Bluefruit ezlink is not accepting my sketch
I don't use a Bluefruit EZlink shield (but I would very much like one).  I use a commodity bluetooth adapter

Make sure you've got the right baud rate - AVR 328P devices generally default to 57600, and ATMega 1280/2560 devices default to 115,200 IIRC.

I've had similar problems, though.   My advice to you is to download and compile the latest version of avrdude, which fixed my problems initially.   Versions 6.0.1 or so will keep retrying the connection, which gives you multiple chances to hit the reset button.

Recently, though, Fedora 19 quit allowing me to upload with bluetooth.   I was able to fix the problem by patching avrdude to retry sending data if the error code is ENOTCONN (107) "Transport endpoint is not connected"

So - if you still have trouble uploading after compiling avrdude, then try my patch at:
https://savannah.nongnu.org/patch/?8272