I have had the same problem once - had to remove the SIM card and re-insert it.

Mine is an old (5yrs plus) Optus SIM card (Australia).

After reading the "Battery Life" tips thread, I was planning on getting a new SIM card anyway.