Hello,
Are you carrying Proxy in your Environment??
If yes, check the Steps provided above by pete.
It could happen that maybe the LiveUpdate catalog or the SEPM installation is damaged.
1) If it is a very fresh installation, just wait some hours
2) Reinstall LiveUpdate without saving the catalog but re-creating it:
http://www.symantec.com/docs/TECH102609
3) Repair SEPM from add/remove programs
If the clients are already up-to-date, it means that they are taking the definitions from another source.
4) Also check the Liveupdate Policy for Symantec Endpoint Protection Manager, if the same is properly configured. The same could be done by:
SEPM > Admin > Servers > Highlight Local Site > Edit Site Properties > Liveupdate
Hope that helps!!