This is not a fully automated method and uses Excel but it will work.
First, get the table sorted internally by UserID and whatever else you want. You can either use a Make-Table query with the correct sort or set a primary index which has UserID as the first field and then Compact the database.
Then add an autonumber field to the table. Write a query which gives you the min(autonumber) and total records per UserID.
In the first row of an Excel file, enter the UserID (A1), TotalRcds (B1), and FirstAutoNum (C1). Write a formula in cell B2 to generate the correct range of random numbers for the User ID:
=INT(B$1*RAND())+C$1
Drag this formula down for as many rows as you need. In column A put the formula =A$1 and drag that down. You can repeat this in another set of columns for as many users as you want to do at a time. You might want to set the worksheet to Manual Calculation so the random numbers only change when you hit F9 (recalc).
In Access, create a two-field table with UserID and a long integer field called RecordID. Paste/Append your Excel data to this table, one UserID at a time. Join this table to the claims table. The Excel file and new Access table can be re-used for other tables.