The problem turned out to be that I did not have the 
 live-media-path=/live/${FLAVOUR}
boot option in the APPEND line of the PXE configuration file.

It was not needed before, I was able to boot 32-bit and 64-bit
flavours of 2011.05 without it.

This does not appear to be mentioned in the release notes,
so the only bug here is in the documentation.

Thanks for grml.