If it's a large transaction and they didn't attach a fee to it, it might take a while. There are other factors that might delay things as well.
Search for your receiving address on both
http://blockexplorer.com/ and
http://bitcoincharts.com/bitcoin/ . If the transaction shows up on BlockExplorer, then it was successful, so something on your machine is screwed up and it's not showing up for you (like Garrett said, perhaps one of you doesn't have the full blockchain downloaded, or it got corrupt or something). If it shows up on the BitcoinCharts page, then it's sitting in limbo waiting to be confirmed, perhaps because there was no fee attached, but he did send the payment. If neither, then chances are he's lying.
EDIT: Or maybe he accidentally sent it to the wrong address! It could happen.