The next thing to check is the list of pending transactions. You can find that here:http://bitcoincharts.com/bitcoin/
If it's not in the list of pending transactions and it's not in the public hash chain, then most likely the other end has not sent the bitcoins.
A transaction should appear in the list of pending transactions with a few minutes, unless a lower than standard transaction fee was paid. In that case, it can take as long as a day to get into the list of pending transaction. Then it takes typically about ten minutes to get in the public hash chain, but it can take longer if there are lots of higher priority transactions or the network just has bad luck.