What's the actual error your getting?  They're not always super descript, but they help us debug nonetheless.

Some things to try (I know you said you tried the obvious, but have to say it again):
1) Plugin enabled
2) Web Services enabled
3) Try both with and without a trailing '/' as the host name.  Different servers react differently to both cases.

Also, from the sites menu, can you click "Edit" and go into the problem site, and click the little icon in the top right with the arrow?  This will tell you if the app can ping the plugin.  It doesn't require correct user info or anything.. it mainly checks that your host/path and 1 & 2 above are operating right.  It should respond with the version of the plugin you have installed.