I had the same problem when I wanted to play Counter Strike Source on my notebook instead of my PC,on which I normally play.
Installed the Steam client and it just wouldn't update. Threw up the same error that you are getting. What I did to resolve the issue was to copy over the entire Steam folder from my PC and paste it over the installation on my notebook. Fired up steam and it took a few minutes to verify the game caches. Then it downloaded some files for a minute and was set. I recommend the same as well if you can lay your hands on someone's already updated Steam installation.