I had a similar issue when I was trying to use an Uno as a boot loader, and I think the trick is that the chip is getting reset part way into the upload. The reasons this seems plausible are :
A - someone mentioned it looked like his board had reset
B - after a half-assed attempt at uploading, my board just starts up the old code (i.e. looks like it reset)
C - It seems correlated to length of code, and I have no issue uploading the blink code, ever.
Anywho, the hardware solution to this software problem is to toss a BFC (10uF or so, I used an electrolytic) between the Reset pin and ground. What this does is it stops the device from getting reset by little transients that I believe are associated with the serial printing stuff.
Hope this works for Y'all, in the end I got it working with Arduino 023 and a 49K program.
EDIT: This worked great briefly but now it has gone back to it's old ways of not working.