I have exactly the same problem. ACR 4.5. Photoshop 1'.'.1. Lightroom preferences not altered from new. (The 8 bit trick does not work).
I did some tests to pin it down for you.
I added Photoshop.exe as the other editor (ignoring the warning message). I can now edit files using Photo/Edit in/Photoshop.exe and that is a workaround that works.
I tried changing the settings for the built-in to the defaults for another editor. In fact I tried all possible settings. It never works.
I tried changing the settings for the other editor to match the built-in defaults, i.e. TIFF, ProPhotoRGB, 16 bit, No compression, and it always still works.
That shows that the settings are nothing to do with it.
Note that what exactly happens when it goes wrong is that it successfully launches Photoshop if it isn't already running, then there is a long wait, then the error message - probably a time-out in the code. So why would it time out if you use the built-in option, and work perfectly if you use the other editor option, even with the same settings? That is a clue.
I hope this all helps you solve the bug, and at least I've given you a workaround.
(XP SP3, 2GB memory, Pentium 4 3GHz, plenty of disk space)
I also just tried it with a JPG instead of a RAW - it fails in the same way.