I came across a snippet of code today which demonstrates connecting two phones in a client/server relationship rather easily (can't find it right now but will post if anyone was interested) but would only work locally. The topic did however spread to the ability to move this to client/client using a third party as a server - I imagine utilising the likes of Google App Engine, Parse, EC2 etc.
My initial thought is that I want this to be as close to free as possible while I am still working on this, the $25 Google developer fee seems the cheapest option to me.
I looked deeper into the Google App/Engine/Game services and feel the documentation on these is sufficient to get myself started on the connectivity side of things.
Thanks for the input guys.