So we are running a handful of different WordPress installations on this server. Here's what we know:
-- We only get this error when trying to retrieve a lost password.
-- Whether we use email or username, the error is still the same.
-- This error does not happen on any other installation.
-- Emails are sent out from this "broken" installation when new users are created.
-- Users who are trying to retrieve their passwords can login if I manually tell them their password.
-- This is a clean installation with no plugins or themes installed (yet).
Where should I look next?