Ok guys, this is kind of useless, but thought I'd report back.
I continued trying various things after my post yesterday. Discovered my video card drivers weren't up to date after all (D'oh!), updated them, no fix.
Downloaded the latest microsoft .NET framework, as several mentioned it was necessary for the game. No fix.
Uninstalled galaxy, ran cmd.exe to delete excess galaxy stuff, I think it was suggest in another thread to type sc delete galaxycommunication and sc delete galaxyclientservice (I'm not sure that's exact, never done that on a game service before) No fix.
I deleted those .dll files multiple times - if you verify your files it will replace them. No fix, regardless of gone, replaced, gone again, etc.
During all this I restarted my computer several times, and uninstalled and reinstalled galaxy several times. No fix.
So eventually I decided I would download the backup copy of the game, uninstall everything, and then just install the back up copy of the game without galaxy, see if I get a fix there. This will take several days, so I left the game installed for now while I download, incase the 1.5 patch releases and maybe fixes things. I wake up this morning to start the download while I'm at work, and for some reason decided to start the game again. And it FRIGGING RUNS. I have no idea why, but it seems like waiting just made it fix itself. It makes no sense, but it seems like just waiting it out fixed it... and I can't think of an explanation why. It seemed like the Galaxy update yesterday broke things, but there was no further update today. I really just can't explain it, but I'm glad it's working again....