So after testing it multiple times before posting, then at least a couple of times afterwards to troubleshoot based on the responses I'd received, I was still getting the error. Yesterday though - I tested once more to demonstrate the behavior to a co-worker working in the same environment...and it worked. The primary field was able to be changed to an autonumber, and did save successfully.
I do not believe I did anything different. I went through and tested again a couple of times, once even following the screenshots I had posted. It has worked every time since.
At this point I'm going to write it off as a bug that has been corrected. Not sure that will help anyone else that experiences this issue - but maybe try it again in a couple of days.
Thanks everyone for the responses.