I have good news and bad news!
The good news is that I just created an InfoPath 2013 form with a REST connection to a SharePoint 2013 site. I am not having any errors trying to connect, and it pulls my data in.
The.... uhh... bad news? That makes it even more likely the issue would be with your server. Do you have access to the SharePoint logs? What about running Fiddler while making the connection to see if you can uncover a bit more info....?