Finally was able to recreate this behaviour locally. Using CentOS 5.3 as dom0, then I took a current oneiric ec2 image for domU, started a javajdk-6-jdk install and got the endless look of multicall failed messages in domU. Meanwhile I could see in dom0 that there was a matching stream of "mm.c:694:* Bad L3 flags 6" messages (6 == _PAGE_RW | _PAGE_USER). Using exactly the same domU image in a CentOS 5,4 and later dom0 works without problems.
Though I could not yet find out what exactly the change is between 5.3 and 5.4 that fixes the issue.