I recently purchased L4D2, and I keep getting the "Steam validation rejected" error message come up when i try to start a server for my mates. I have also noticed it when i try and join a game they are in. The steam support forums are useless in this instance and I am looking for some assistance with the matter. My other search in these forums brings up an archived thread with no answer...
Agree with OvrClkr on this one. This is sort of like having a game say your CD-Key is invalid. You'll probably have to contact Steam to get this one fixed.
The other option, just in case, would be to go into the Options within Steam (options for L4D2 specifically) and have it scan for any issues. Sometimes bugs like this are fixed as Steam updates file for the game.