Fedex address changes ..
..are acceptable only for 'current' inprocess packages!
You cannot make an advanced change of address request for a fedex package ..thats what the fedex guys told me when i wanted to find out for change of address just in case.
which means, once you lookup the on Fedex that your package has been shipped, per someother member on this site, you can ask for a re-direction (though i dont think they will re-direct, you can only have that held at the Fedex office and have one of your friends pick it up - u have to provide a copy of the tracking receipt to your friend).
Good luck
Rox