here's another idea, similar to the old phone having a message saying to call you at your new number:

if your "old" phone company has call forwarding, you can forward all your calls to your new number (mine is by dialing *72-123-555-1234 and hitting send, YMMV of course). tell everyone about the new number, but leave this on for a couple of months, for anyone who missed the announcement. this does use minutes (at least with alltel it does). also, when people call you and you miss the call, you can call them back with your new number, and then they'll have it.