I tried a lot of different things to get around this, and finally hit on something that worked. Unfortunately my last attempt included several tweaks, so I'm not yet sure what the magic bullet was...
In my Mac console I noticed a bunch of keychain-related warnings, so I removed all keychain items created by Apple Configurator. Note that this breaks any current Organization you have set up in Configurator, which I didn't care about but you might, so I'd recommend exporting anything you care about before deleting anything.
MacOS error: -25304 // errKCInvalidItemRef = -25304
CSSM Exception: -2147417855 CSSMERR_CSSM_INVALID_ADDIN_HANDLE
MacOS error: -25304
CSSM Exception: -2147417855 CSSMERR_CSSM_INVALID_ADDIN_HANDLE
MacOS error: -25316 // errKCDataNotAvailable = -25316,
MacOS error: -25305 // errKCInvalidSearchRef = -25305
could not enable test hierarchy: ApplePinningAllowTestCertsAppleSWUpdateSigning not true
could not enable test hierarchy: ApplePinningAllowTestCertsPackageSigning not true
could not enable test hierarchy: ApplePinningAllowTestCertsMacAppStoreReceipt not true
could not enable test hierarchy: ApplePinningAllowTestCertsAppleIDAuthority not true
WARNING: SecPolicyGetOID failed to return an OID. This function was deprecated in 10.7. Please use SecPolicyCopyProperties instead.
0x608000277c00 opened /Users/ericm/Library/Keychains/login.keychain-db: 1383760 bytes
CSSM Exception: -2147415780 CSSMERR_CSP_INVALID_KEYATTR_MASK
CSSM Exception: -2147415780 CSSMERR_CSP_INVALID_KEYATTR_MASK
In Configurator preferences I deleted my old organization, and I later had Configurator create a new one during the Prepare process.
I signed out of iCloud on the device.
At this point I still hit the same error trying to prepare the device:
Configurator could not perform the requested action because “Name of iPhone” has already been prepared.
Click “Erase” to erase and prepare the device again. All content and settings will be deleted. This cannot be undone.
I'd been through the Erase process enough times this week to not have much luck that it would work, but I decided to try it one more time, and also log into a different iCloud account (that this device had never been associated with) when the device came back up. In the end the device was Supervised.
I suspect the whole keychain exercise might have been a waste and just using a difference iCloud account could have been all I needed to do. If I get a chance I'll try to narrow it down on another device I've been having problems with.