Just a thought, I have had similar problems with patching, caused by updates to my antivirus program, after update the firewall would block the gameclient.exe file and prevent patching, so I would check your firewall settings anf make sure its not blocking the gameclient.exe, should be set to outgoing.
I also had the exact same issue, very frustrating indeed. However for me I simply turned off my firewall and it worked! The patch is coming down right now, when it's in the firewall will go back up. Maybe it was just a coincidence and STO sorted it out but who know's.
UPDATE : As soon as the patch was downloaded my character screen showed, I started up one of my toone's and as it was loading I reactivated my firewall, as soon as I had done this the message "server not responding..." appeared and it disconnected me from the server! I deactivated my firewall and repeated and I am not in and playing STO! I would say a major programming glitch once again from STO, so I would say you will have to allow STO itself into your firewall.