greasonnet
https://grapheneos.org/install/web#enabling-oem-unlocking
Specifically
“For the Pixel 6a, OEM unlocking won't work with the version of the stock OS from the factory. You need to update it to the June 2022 release or later via an over-the-air update. After you've updated it you'll also need to factory reset the device to fix OEM unlocking.”
It seems like you followed those directions. I’d do it again one more time ensuring the device is fully updated then factory reset in that order.
I would use WiFi as well (But that’s my own suggestion).
Otherwise may have to start looking into returning it and getting one from Google as suggested.
For all we know the Amazon could be stocking batches of unsold phones from other carriers that have the restriction in place.