The funny thing about my site... I logged in to wordpress admin, and it said there were 5 admins. I clicked on the list and saw 4 admins, all friendly users who I recognized. Who's the fifth? And the funny thing is, something blinky happened when the page loaded, like a user was showing up and then being hidden client-side.
So I logged into phpmyadmin to go straight to the database, and ran this query:
SELECT u.ID, u.user_login from wp_usermeta m, wp_users u WHERE m.meta_key = 'wp_user_level' AND m.meta_value = 10 AND m.user_id = u.ID
Sure enough, it showed five people, the last one was a new user just added today who I'd NEVER seen before.
So I noted the data then ran:
DELETE from wp_usermeta WHERE user_id = 312
DELETE from wp_users WHERE ID = 312
(because my user in violation had ID 312... use whatever number you found, obviously)
You should still upgrade your wordpress version cleanly but if you clean your user table this way, I think it's safe to backup and restore your user tables. If you're still worried, just replace all the passwords in the database and tell your users to do a lost password retrieval.