A likely cause is that Calculation is set to manual. To change this to automatic in the various versions of Excel:

• 2003: Tools > Options > Calculation > Calculation > Automatic.

• 2007: Office button > Excel options > Formulas > Workbook Calculation > Automatic.

• 2010 and newer: File > Options > Formulas > Workbook Calculation > Automatic.

On Mac:

• 2008: Excel Preferences > Calculation > Automatically

In some cases you may prefer to keep it set to manual, for example if there are many heavy calculations to perform. In such cases, you can simply press F9 when you want the calculations to update.

Confirm with Excel 2007: Office button > Excel options > Formulas > Workbook Calculation > Automatic.

Short key to refresh

Ctrl+F9

I had a case of this just now on Excel 2010: a particular spreadsheet that would not auto-recalculate. I changed the setting as indicated above; but the auto-recalculate still did not work, and upon rechecking the "Calculation" option, found it had reset itself back to "Manual" all by itself. Three attempts later and it was still adamant it wanted to be "Manual" and nothing else.

So here is my solution to the problem:

Copy the contents of the spreadsheet to a new one, and deleted the old one (it wasn't a particularly important spreadsheet, thankfully), and everything was fine. I can only assume that somehow the file had become corrupted.

A good reason to keep backups.

Reposting this snippet that user RFB had (inappropriately) attempted to edit into my answer:

A possible cause is that the Office Prefs file is corrupted. In OSX this can be found in:

Library/Group containers/*.office/com.microsoft.officeprefs.plist. 

Delete this file and restart the OS. A new plist file will be created when Office is restarted. Formulas recalculated again perfectly.