here is my workaround that consistently works not only at boot or reboot but also after suspend/hibernate...
--> just install using synaptic the bluez package from blueman ppa (ppa:blueman/ppa); it only exists for maverick but it installs ok in natty.
before I tried
1) kernel upgrade from natty proposed
2) /etc/init.d/ bluetooth restart in /etc/rc.local
1) did not work and 2) does not work after suspend/resume
hope this will help someone trapped in natty and lazy as myself to downgrade to the good old maverick...
PS: after having to deal with this and the infamous 1-pixel tray icons bug (https://bugs.launchpad.net/ubuntu/natty/+source/unity/+bug/767095) I wonder how it is possible that natty ever came out of the beta (not to say alpha) status