Warning-STEAM message "We've come up empty"

[Screamadelica]

I had this problem also. Bought a standard box version (made in Australia) from EB Games, intended as a backup copy to the Collector's set, and have held off installing until the game was in some kind of a workable state with the last patch. When I went to install it, I got the same message - "Already activated", etc.
As I had not installed it within the 90 days time period Steam will do nothing. Interestingly though, the Collector's set installed fine. Also got the same "Already Activated" message with another brand new game, also bought from EB. In both cases the good folk at the EB store swapped the games for a replacement copy which installed fine. Something strange is definitely going on here.