Could you add some more information please, were they the same OS? did the steam client output any errors? If not, could you try again with steam running in a terminal and paste anything it outputs - might help.
the steam client did not output any errors, and the terminal did not give anything related to the restore:
Generating new string page texture 169: 64x256, total string texture memory is 5,69 MB
saving roaming config store to 'sharedconfig.vdf'
roaming config store 2 saved successfully
Installing breakpad exception handler for appid(steam)/version(1368229716_client)
Installing breakpad exception handler for appid(steam)/version(1368229716_client)
saving roaming config store to 'sharedconfig.vdf'
roaming config store 2 saved successfully
The backup was made on Ubuntu 12.10 and I tried to restore it on Ubuntu 12.04
The new Steam client beta today should fix this.
The problem seems to have returned
Nothing extracted yet.
I made a steam backup of Left4Dead2, Portal Beta en Waking Mars. When I restored them on another PC all 3 of them wanted to redownload the complete game.