I had this problem with my first Droid. DL sensor test from the Market and see if the value for the Proximity sensor changes from 2.14xxxxxxxx to 3.0 when you put your finger over the sensor (top left corner). If there is no change, then take it to VZ for exchange.
DL'd sensor test and the proximity sensor doesn't change at all. :icon_ cry: I did cover and uncover the sensor and there was no movement in the values at all.
PROXIMITY:
0:3.0
1:0.0
2:0.0
Yep, bad sensor. I had purchased mine online and swapped it for a brand new one at a store. I had only had it for a few days though.