Remote Erase through Find my iPhone — Changed Password My iPhone was stolen (with the SIM card ejected, on my seat). When I logged in to iCloud it made me reset the password, which meant my Apple ID password was now different from the one on my iPhone when it was stolen.

I figured there was no way I could find my iPhone, so I hit Erase. 3 days later I got a message saying my phone was erased. Is that a lie, because my phone had a different iCloud password on it than when it was stolen? It was running iOS 8.

When I first checked Find my iPhone it was offline and pending erase. Then I got an email at 1 am saying it was erased.
Changing your password would have no incidence on whether your iPhone was able to receive an Erase command from iCloud. The reason it took 3 days for your iPhone to become erased is that without a SIM card it had no Internet connection.

What must have happened is the thief inserted a SIM card into the iPhone after a few days, at which point your iPhone connected to the Internet and received the command from iCloud to erase itself, which it did. That’s when you got the confirmation.

You can read up more at iCloud: Erase your device.


  After you set a device to erase
  
  
  If your device is online, the remote erase begins. A confirmation email is sent to your Apple ID email address.
  


Addendum to address lingering concerns:
Unless you can verify that the email is not legitimately from Apple (which you can do by viewing the headers on a desktop mail client), I’m confused as to why you would insist on believing that Apple is lying to you. Apple has a vested interest in making sure your account and devices are safe.

Your iPhone is linked to your iCloud account by a secure token rather than by sending a username and password every time a connection is made. When your iPhone connected to the Internet, iCloud instructed it to wipe itself before telling it its session was expired. It would make no sense for a logout request to supercede a wipe request.

In fact, when a device is compromised in any way (such as theft), changing your password immediately is a good first step towards protecting your account. If changing your own password helped the thief get into your device (by disabling remote wipe), you’d be even more at the mercy of said thief.