Hey there,
I was pretty surprised when I wanted to withdraw some BTC at Mt Gox. I saved the Address in the past and just clicked it in my bitcoin client and sent some bitcoins. Then i checked Mt Gox again and realized that the withdraw address changed.
Are my bitcoins lost?
No, the address changes every time. You can still send coins to "used" addresses as well. It will take 6 confirmations before they show in your account.