The problem turned out to be with the token that Live REST API was returning in C++. It seems the correct information was not being requested through the WinRT API used to authenticate with the Live Service. Fixing that fixes this issue.
The correct code snippet has been posted on this MSDN Forums post.