I have no experience with retail purchases of games from ValvE since they launched Steam, so someone else should comment on whether there's something to be done about this from your end.
In case you really are screwed, then it's your luck that you've been screwed by EB Games. You can just go back and reclaim your money. EB in turn is screwed by the guy who turned in his copy after registering it on Steam. I'm even amazed that EB sells second hand Steam games, to me that looks like a recipe for disaster.