IT IS A PROBLEM WITH YOUR BACKUP- PLEASE READ
I had this problem weeks ago, right around the time I updated my iPhone 3gs to the 4.0 GM build.
I found that by resetting my Network settings under General- Reset, It would correct the issue temporarily.
However, when I got my iphone 4 and restored my backup, I had the same issue again with the proximity sensor not working.
It seemed to be an issue with my backup files being corrupted. The proximity sensor would work fine when I restored the device to factory settings, but when I restored my BACKUP, it would cease functioning.
I found the only way to correct the error was to set up the iPhone 4 as a new phone and import my contacts again.
Try doing a complete restore, but DO NOT RESTORE YOUR BACKUP!
Test it first to see if the sensor works properly.
Edit- guess this didn't help people. It definitely fixed my problem, and bear in mind that this problem FOLLOWED me across devices (From 3gs to 4.0). I even took my 3gs into the shop and got it replaced. When I restored from the backup of the old device, it stopped working again.