Dustin - Ross' answer made me think - could it be that your PC 'thinks' the game is already running? Has the PC been compleately shut down, not just a restart, standby or shut down then immediately (less than a minute) started since you started getting this message? I have had strange problems like this that won't go away with restarts or shut down and start again - but have cleared following a either an overnight shut down or a shutdown - disconect power supply - press on button (while still unplugged to use any residual power) - then plug in and start up.. I think its to do with clearing memory totally and restarts don't give time for everything to totally clear..
Also somewhere in Steam is an option to 'check game file integrity' or something along those lines - I think it might be in the menu if you right click on a game, although I am not logged in at the moment so can't find it - you could try running that too.