I bought Braid on my old 360, but I'm now on a new one. Redownloaded it, and played while logged into my account, which it was bought on, and when I quit, no progress is stored.
I remember reading before when some people would play the game it would play as if it was a demo even though they were logged on. My only suggestion is have you transferred the licenses to your new 360?
Edit: Just saw your gamer profile...says you haven't played any games or any achievements. Was this new 360 used? Maybe it was banned on Live and you're having problems with it now. That might be something else too