I am with Rackspace already (love them, btw). We manage our own servers. In my case, it turned out to be something at the server level that was preventing mail from being sent out via any php forms. It ended up not just being the WP plugin but ALL of our contact forms, even the ones on non-WP sites. My server guy had made some security adjustments which resulted in being a little too secure, not letting mail through. As soon as he changed those settings, we were able to use the plugin.
I hope this at least helps some folks out there who may be having problems and have already ruled out the other possible causes.