I just tested out the http://31daysofwindows8.com/push and it worked fine for me. The cloud service does need the SID and key to authenticate with WNS on behalf of your application, so in that sense they are associated, but for the http://31daysofwindows8.com the association was quite temporary as you just enter them in as input (and be aware they are in clear text with that tool).
You would need to use the URI you got from your Windows 8 app (via CreatePushNotificationChannelForApplicationAsync) using exactly the same SID and key that you are using to obtain the OAuth access token. All that would be appropriately setup for you when you associated that app with the profile in your store dashboard.
It sounds like this is just what you did, but the error you're getting has the hallmark of trying to use a channel URI obtained with one SID/Key to send a notification authenticated with a different SID/Key. Note that if you're uninstalling and reinstalling your Win 8 app (an option on the Debug tab in Visual Studio), this will also invalidate a previously obtained URI; however, in my case, the 31daysofwindows8 site reported a revoked URI, not a "incompatible" one.
As for your cloud service that times out, are you url-encoding the URI when you send it up?
Lastly, it's a bit of a tangent from your specific question, but if you haven't looked at Windows Azure Mobile Services, its role is precisely to take away the pain of rolling your own service to do all this. There's a completely free tier and there's always the ability to add more horsepower when your app goes wildly successful.