I can't find any official announcement of it, but it looks like there are now official HVM AMIs available with the release of 7.4: https://wiki.debian.org/Cloud/AmazonEC2Image/Wheezy
Edit: Not sure whether there was a real problem before (vs PEBKAC), but the new images _do_ reboot successfully (takes about 2 minutes). Now to get systemd running...!
I think they were just looking for a scapegoat in that particular case.
For anyone reading along, reboot does now work, and I was just able to install systemd (apt-get update, apt-get install systemd, edit /etc/default/grub, edit /etc/fstab to remove the systemd-unsupported nobootwait line, update-grub, init 6). Thank you Debian cloud team :-)
[1]: https://lists.debian.org/debian-cloud/2014/02/threads.html