I have been looking for a solution to this problem for a while now and I am happy to say I finally found out why I was not able to boot into safe mode. Everytime I tried it would start and then before it reached safe mode my computer would restart. It was caused by Nero 6 Incd 4 installed on a Windows xp system, I uninstalled Nero and now it works great. I am going to see if they have a update to fix the problem because I prefer to use Nero.
I just wanted to bring this up, just in case anyone else has had this problem. I had written months ago about this and never had any luck. Hope this helps !