Hello narflack,
The reason that the old phone is still showing up is outlined in this article named iCloud: Troubleshooting Find My iPhone, iPad, iPod touch, or Mac found here: http://support.apple.com/kb/TS4006
This section in particular:
Previously-owned device appears in Find My iPhone
A device will appear in your device list when you log in to Find My iPhone as long as Find My iPhone is turned on in the iCloud Settings or System Preferences on your device or Mac. Be sure to remove your iCloud account, along with any other personal data, from your device or Mac prior to selling or giving it away. See this article for more information. If the device is currently offline, you can remove it from the device list by clicking the X icon (Remove) to the right of its name (at icloud.com/find from a computer) or by swiping over the device name in the device list in the Find My iPhone iOS app and tapping Delete (in Find My iPhone 1.3) or Remove (in Find My iPhone 2.0).
Note: If your device is still configured with your iCloud account, the next time the device connects to the Internet, it will be added to the Find My iPhone page again.
All the best,
Sterling