If you haven't already, try restarting the iPhone by holding the Sleep/Wake button until the red slider appears> then slide to turn off> and turn the iPhone back on by pressing the Sleep/Wake again, as described on page 34 of the iPhone User Guide.
http://manuals.info.apple.com/en/iPhoneUserGuide.pdf
If the issue persists after restarting, try contacting the cellular service provider and having them verify the account is still active.
You can also try restoring the iPhone, to rule out issues with the software running on the iPhone. This article:
http://support.apple.com/kb/HT1414 will walk you through the process.