My initial comments said I was on a 11.04 system, which is incorrect; this is happening on 11.10, as the bug metadata correctly states.
I just tested this on Ubuntu 10.10 and Ubuntu 11.04, and both versions have a valgrind that works with 32-bit binaries on a 64-bit system, so this is definitely something that worked recently, and definitely broke in 11.10.
Quick follow up:
My initial comments said I was on a 11.04 system, which is incorrect; this is happening on 11.10, as the bug metadata correctly states.
I just tested this on Ubuntu 10.10 and Ubuntu 11.04, and both versions have a valgrind that works with 32-bit binaries on a 64-bit system, so this is definitely something that worked recently, and definitely broke in 11.10.
--ryan.