SimonG: Well, you don't need Origin to play it, you didn't buy it on Origin and you got a coupon. I think you really can't complain.
Also, you might try again later ;-).
Foxhack: Their help files and forums contradict themselves. All I want was a place where I could download and resume the download, like Steam does.
What is the point of them having such a service and saying all games past 2009 would work, if they don't?
Bulletstorm is a special case because it was published by EA but the devs were People can Fly. They most likely took the decision to use GFWL for DRM instead of SecuROM or EA Core like most EA games. Apparently, GFWL keys are not in the same format than Origin keys.
Unfortunately, the support guy that talked with you didn't want to help you. Maybe you'll have better luck if you try again. There was a forum thread where one of the Origin developers talked about Bulletstorm and that people should contact support to get it activated on Origin. Maybe if you find that support will listen to you.