Ok so while I don't know specifically what was happening under the hood, so to speak, the problem was caused by my installation of the "Office SharePoint Designer 2010 (x86) – Technical Preview".
Uninstalled that and the Web Service Data Connection appears to be working as normal.
Thanks,
Ben