This was asked long ago, but I just ran across the same problem. My fix is very roundabout, but it did work. It only works for point feature classes and assumes that you want to use sequential integers starting at 1, but just in a different order than the ObjectID you have already.
- Use the Add XY Coordinate tool to add coordinates to your feature class if it doesn't have it already.
- Select all features and copy them.
- Open a new spreadsheet and paste the whole table.
- Delete the existing ObjectID (and Shape) columns.
- Move the field you want to use as ObjectID to Column A and sort it.
- Save the table as a text (tab delimited) table (others will probably work as well).
- In ArcCatalog, right-click the table and select Create Feature Class.
- Use the Point_X and Point_Y fields for your coordinates.
After I did this I had a new point feature class with the ObjectID exactly in the order I wanted to use. I hope this helps someone else.
Cheryl