I do get a returned mail notice from USCIS before this one

I got an email yesterday afternoon before the above one,

Current Status: Notice returned as undeliverable.

On March 21, 2007, the post office returned our last written notice on this case as undeliverable. This can have serious effects on the processing of this case. Please call 1-800-375-5283 to update the mailing address so this notice can be re-sent.

So I called USCIS. The lady repeated the same message as "On March 21, 2007, we mailed the document we manufactured based on our earlier approval of this case, and mailed it to the address on we have on file. You should receive the new document within 30 days. If you do not, or if you move before you get it, call customer service.". She won't allow me to change the address and even won't check my current address on record. She said I should wait 30 days.

My case is EB1a.