Also... if this is a new watch has it been updated to Watch OS 2.01? Perhaps it is still on Watch OS 1 and the apps require OS 2?
As batting1000 said, it could be as simple as restarting the watch (or both the iPhone and the watch). I have had some apps or updates refuse to install and restarting the watch has fixed the issue.
Sean