This can be done quite easily
Your on the right track, you just need to update all the existing records and then it will work going forward.
Starting from the beginning:
First thing to do is to setup your UniqueID field in the database, and set the Auto-Enter option for Serial number to On Creation and specify your next Value and increment by.
Now in your records, make sure you are in all the records in your database, Records > Show All Records. Place the UniqueID field on your layout and click into it and go: Records > Replace Field Contents...
In the Replace Field Contents dialog select the option for 'Replace with serial numbers:' and the Initial Value should match that you input in the Auto-Enter option.
Tick the option to 'Update serial number in Entry Options?' If this option is not selectable then there is a problem in the Auto-Enter settings.
And click Replace.
This will set the serials for all the records and also update the next value in your Auto-Enter options.
Once this is complete go back into Define Database and the Auto-Enter options for your UniqueID field and tick the option for 'Prohibit modification of value during data entry'
Let me know if this makes sense or if I need to expand on anything for you.
Worked like a charm! Thanks!