I know this thread is really old, but in case I run into this again and I've forgotten, I discovered that my form template was too large. The InfoPath client seems to only allow 30 seconds for a response from InfoPath Forms services on form verification. But the web service response actually does complete. This can be seen by using Fiddler to capture the traffic. When the response is viewed in XML format, it lists all the verification messages. Unfortunately, since my form isn't getting any smaller, I've resorted to first running the verification, weeding through the XML response in fiddler, and then publishing it to SharePoint without verification.
Fiddler can also be helpful to troubleshoot other issues too with Publishing/Verifying since the InfoPath Client is communicating with a web service over port 80.