What do you get from the following command after a reboot, but before you chmod it?
[gene@Mobile-PC ~]$ ll -d /dev/shm
drwxrwxrwt. 2 root root 320 2009-12-02 12:40 /dev/shm
As you can see, mine is 777 and i've never touched that entry in /etc/fstab. As far as I know, it's always been:
tmpfs /dev/shm tmpfs defaults 0 0
EDIT: You shouldn't need to do this, but adding umask=0 to the options in /etc/fstab will make the mount point permissions 777.