I have this problem too. I trimmed the plastic off the top of the headphone's plug enough to allow it to slide in.
They sell some adapters that will solve this problem for you... But as a quick fix in the field, trim the rubber off the boot and it should fit.
Read this:
http://reviews.cnet.com/4321-6448_7-6581633.html
Read this:
Macworld | Review: iPhone headphone adapters
I don't see my self buying an extra piece to carry around in my pocket as forgetful as i am. Read this for an example of trimming:
http://www.turbozen.com/howto/iPhone...one%20adapter/
That's one of the few minor reasons i'm upgrading to the 3g since it don't have the recessed jack.
