Many TUAW readers have noted that their replacement power adapters have been received. In addition, Mac|Life has posted some pictures of their replacement, noting that they're shipped in a huge box. They also have a side-by-side comparison of the defective adapter and the replacement -- the only difference being a green dot on the new one.
You can order a replacement on Apple's website, or visit an Apple store starting on Oct. 10. If you exchange your adapter at an Apple retail store, you will need to have your iPhone 3G and your affected adapter.