After trying many different ways to no avail, I got it to work this way. I'm using Windows 7 64 bit.
It seems to be a combination of drivers and the sd card.
This is for users who already know most of the steps but still can't access Recovery, and have tried every single method with no success.
1. First thing, in your usb driver folder in your sdk dir, we need to edit the "android_winusb.inf"
Look for and add this under [Google.NTx86] and [Google.NTamd64] lines.
%SingleAdbInterface% = USB_Install, USB\VID_0BB4&PID_0C9E
%CompositeAdbInterface% = USB_Install, USB\VID_0BB4&PID_0C9E&MI_01
%SingleBootLoaderInterface% = USB_Install, USB\VID_0BB4&PID_0C94
and save. (credit goes to onodontbescurred)
2. Plug in the phone, an open device manager. Look for Android, click the drop down menu, right click and update the driver. Follow the steps and point it to "android_winusb.inf" If it asked you to restart just do it.
3. After restart have your phone plugged in go back to the device manager. Leave device manager on for the next steps.
Turn your phone off, with the usb still plugged in. Press and hold the optical Trackball and press power. Once in the menu press power again. Wait 5 seconds. At this time you will see in Android in the device manager just like before. Do step 2 again and update the driver. Yes you have to do this again. Do I know why, no. Does it work, yes. After you do this go ahead and tab down to recovery, wait, then hold down volume up and power, from here reboot the phone. We'll be back in a second.
4. Now from here, ether use another sd card, or copy your intire sdcard to the computer (you can copy everything back later).
5. Now from here your going to have to Take out your sdcard from your phone to Format your sdcard. To do this the right way, your going to have to use a card reader of some sort. The reason being is formatting the card through the phone won't work, because files are put back on by the phone. After you have your sd card in your reader, just right click on it and format it. I'm used the extra free 2gb sd card that came with the phone.
6. Leave the card out and turn off your phone. Then insert the sd card you formated back into the phone.
7. Open up cmd, and restart the loop.
8. Refollow the steps (credit to you_eeeeeediot @ XDA for the new procedure)Press and hold the optical Trackball and press power
Once in the menu press power again
Wait 20 seconds for it to do its bit
Plug USB in and wait another 10 seconds for your computer to detect the phone
press menu down to highlight "recovery"
wait 20 seconds
the screen should change from "error: device not found" to "exec '/system/bin/sh' failed: No such file or directory (2) -"
9. If succesful, you can follow Perunnerseth's instructions here.
Root process, my regurgitation of it, with Perm Part added.
10. Send me a Wonka Bar with a Golden Ticket.