If the phone's IMEI associated with your account? If you bought it from another source, it wouldn't be and that is why the database won't locate the IMEI. Or even if you bought it from AT&T on your account, it just might not be provisioned properly on your account. I've seen lots of folks have luck with bringing the phone into an AT&T store and having the IMEI linked to your account, then the SIM unlock should work.
Please click the "Thanks" button if you found a post helpful!
Phone: AT&T HTC One (M8)
Tablet: Samsung Galaxy Tab Pro 8.4 (WiFi only)