Weird, perhaps, as you already thought of yourself, starting the system in "safe boot" mode works. If that doesn't work, try booting from a CD/DVD, go to the command-line, and try from there. The problem is I can't test this for you as my main system is a Mac and I only have a 32 bit version of Windows 7 in a VM (and that, the test version Microsoft made available to the public).
Sorry,
Hayo