Seems like I found the issue:
In our configuration we had this line:
<connector name="ajp" protocol="AJP/1.3" socket-binding="ajp" enabled="true">
As you notice the scheme attribute is missing and thus the protocol seems to be undefined.
Adding scheme="http" resolved it.
The problem was that in JBoss 7.1.0.Final following the instructions I linked above yielded a result that contains:
Additionally, the server didn't complain about the scheme missing on startup.
Trying to do the same in JBoss 7.1.1.Final yielded an error at startup, telling me that the scheme was missing.
So I guess the issue was misconfiguration in conjuction with a bug (not complaining about the misconfiguration) that seems to be fixed in JBoss 7.1.1.Final.