Index corruption is the first thing that comes to mind. You could try dropping any indexes you currently have on your autonumber field, then re-creating them. If that doesn't get it, you probably need to import all your db objects into a new .mdb.
Also, make sure you have the latest service pack (SP 8) for the Jet engine installed (SP 8). You can get it at http://support.microsoft.com/default.aspx?kbid=239114
. There was a MS bug report a while back about autonumbers duplicating old values in some version of Access. Don't know the KB number off hand, but updating Jet was the fix.