Unable to upload with different messages on Mac/PC

Okay I've searched the boards, but can't make heads or tails out of what has happened here. It's not because I've got a Atmega 328 and need to select the right board, and the correct ports are selected (I only got the one on my laptop and nothings changed on my Mac), plus when I press upload it does start to blink, but just stops.

On my laptop running Windows XP and version Arduino 16, when trying to upload the Blink example, just to have something generic to test with, I recieve the following message:

UPDATED with verbose output:

         Using Port            : \\.\COM7
         Using Programmer      : stk500v1
         Overriding Baud Rate  : 57600
avrdude: ser_open(): setting dtr
avrdude: Send: 0 [30]   [20] 
avrdude: Send: 0 [30]   [20] 
avrdude: Send: 0 [30]   [20] 
avrdude: Recv: 
avrdude: stk500_getsync(): not in sync: resp=0x00
avrdude: Send: Q [51]   [20] 
avrdude: Recv: 
avrdude: stk500_disable(): protocol error, expect=0x14, resp=0x51

avrdude done.  Thank you.

While on my Mac mini, also running version 16, I get this message:

avrdude: stk500_recv(): programmer is not responding
avrdude: stk500_recv(): programmer is not responding

I've gone through the troubleshooter on the website and can't find any logical reason for this behaviour.

Could the atmega be having some issues?

Forgot to mention it's a Duemilanove, and as mentioned I'm on both Mac and PC, and I have been able to upload ever since I got it.

UPDATE:

This might have been happening before, but I did not notice it. I just noticed that when connecting the Arduino to my computer I recieve a strange LED blinking sequence. I will write it down one line per blink, with the LED names on each line, so if RX & TX is on the same line, the blink at the same time. Empty line means slightly longer pause then just the blink of the eye.

RX TX
L
RX TX

RX TX
RX TX

L
L
L

L
L

L
L

L
L

L
L
L

Beeing frustrated not getting my Arduino to work again I ordered a new one, but at the same time I ordered a new Atmega, as it is the only part I actually can swap out with ease.

The result was no change, I am still unable to upload any code.

Since the last post, but before recieving this new chip, I've connected the broken Arduino to my Windows XP laptop and a message stating that Windows could not recognize the device has appeared, but it's not every time or regularly.

Could the USB chip have burnt out? And if so, is it possible to program the Arduino in another way? It would be nice to be able to use it even though the USB seems to not be working.

It's possible the FTDI (USB) chip is broken or mismounted. If so, you should be able to get a replacement.