I had a similar experience yesterday.
I used the Contact Centre Enterprise sandbox and it worked pretty well.
I could access Finesse using REST via soapUI and also used XMPP via Pidgin or Smack.
But I could not login to the Finesse desktop - got a black box saying "Connecting" then a timeout error message or an out of service error as above.
Looking into this right now and will get back to you shortly.