I'm in the same boat. I just upgraded from Kaspersky Internet Security 2011 (which has never been an issue for me with FFXIV) to 2012 earlier this week (around the time of patch), and now have had the same issues today.

Earlier wasn't even able to get the login details screen.

Have just uninstalled Kaspersky completely, and am now able to get to the "start" button that should load to character selection screen, but after a few seconds of black (with the tiny "loading" icon in the corner), it goes to:

13001 The lobby server connection has encountered an error.
Error Code: 0
Status: 0
TIMEOUT

I have turned off Windows Firewall completely (normally it is off, so can only think that the Kaspersky upgrade turned it on) and am just re-starting now. Will keep you updated.