I know this ain't helping, but I am trying to change mine to letter, but it keeps on going back to A4. I still think it works with your printers' paper size...
I think it works with printer paper size as well. Go to your printer in Control Panel, right click and select Properties. Go to the Advanced Tab. Click Printing Defaults, and make sure that the paper is set to A4 there. It's something that sometimes gets overlooked.
The paper size has been saved in the document you are trying to print. many printers have an option to auto resize letter to A4, loo in your printer options from the file/print screen. If the option isn't there, you can probably override the paper size at the printer. How, is dependent on the printer. RTFM.