I've seen this a few times in Eclipse, so far the best solution I've found is to simply restart Eclipse—seems to fix it every time.
I've had the issue occur seemingly randomly, even on a project I've been working on for a few hours it'll sometimes just start throwing this up every time I try and save to server.
If you have "build automatically" option set, then whenever you save the file locally Eclipse will try and save it to the server.
Otherwise you have to explicitly use "Force | Save to server".
--edit--
Since you have the build automatically checked, it must be something else. Perhaps the org is locked at the time because of running tests?
Have you looked at the Eclipse progress window? (you can add this to your view)
When you hit save, this should be where you see the status of the save to server when build automatically is checked.
What do you see now in your progress window if you try and save? Is there an error message?
edit2--
Another possibility is that you have somehow enabled "work offline" mode on your project. In this case it will still do the "save to server" on demand but not for normal saves even when build automatically is on.
And when you select it you are warned
edit3--
One quick check to make would be to ensure that the classes are referenced in your package.xml Although, since you find it works when you manually "save to server" then this should not be the problem. Check this in Force.com | Add/remove Metadata Components and then ensure your class is listed there.
Other than that, can you try and pin down particular files that are affected? Is it a repeatable problem - try force "save to server" on a file.
Then add a line or comment and do a normal save.
Observe if the "polling server" progress appears.
Check in the Problems window for anything like this
Once a file is out of sync you will need to resolve it and force save (this can happen if there is a problem communicating with the server or if someone else has updated the file and the instance copy is more up-to-date than your local one).
Best Answer
As @DavinC stated, make sure that you right-click on your Project > Force.com > Work Online not Offline
It seems that this setting may toggle without you have done it willingly. In my case it was an old existing project which form one minute to the other stopped working.