Kernel linux-image-2.6.35-25-virtual fails to reboot on EC2

Binary package hint: linux-image-2.6.35-25-virtual

After upgrade to linux-image-2.6.35-25-virtual the instance fails to reboot when issuing 'reboot' at the prompt.

Steps to reproduce
1. Start an instance from the official Maverick image, ami-cef405a7 (m1.large)
2. Log in to the image and sudo su to root, running kernel is (2.6.35-24-virtual)
3. Issue reboot.
4. Wait for the instance to reboot and become available again (10-30 seconds)
5. Repeat step 2-4 a couple of times to verify that the instance is rebooting fine.
6. Run aptitude update && aptitude upgrade - aptitude suggests kernel upgrade to linux-image-2.6.35-25-virtual.
7. Upgrade kernel to inux-image-2.6.35-25-virtual (aptitude install inux-image-2.6.35-25-virtual).
8. Issue reboot (this works as we are still on the old kernel)
9. Wait for the instance to reboot and become available again.
10. Issue reboot
Expected outcome: Instance will become available as in step 4.
Actual outcome: After several minutes the instance is still not available. Using ec2-tools or AWS Console to issue a number of hard reboots eventually makes the image available again.

Rebooting again will give the same behavior - the instance will not start until it is forced from outside. Judging by the console output the instance get stuck in:
 * Will now restart
[ 17.059492] Restarting system.

Reverting to old kernel will make the instance rebootable again (after one messy reboot to get rid of the failing kernel).

Output of lsb_release -rd:
root@domU-12-31-39-09-F4-A0:~# lsb_release -rd
Description: Ubuntu 10.10
Release: 10.10