Checkin cannot proceed because the policy requirements have not been satisfied.
I got this message while checking-in a file after the fresh installation of Visual Studio 2008 Professional and TFS client.
This message disappeared after installing VSTS 2008 Power Tools. The download link is provided for your quick reference here.
Please share your feedback if the same fix has helped you.