Hi Keith,
This is not directly related to the Store module. PayPal DO NOT authorize to use a previously used order number. If you previously test an other store module/product with PayPal and used order number range from 1 to 1434 (as a sample), you have to use an order number higher than 1434! If you don't know what is the higher number is, ask the PayPal support.
If you can't use Enterprise Manager or similar db tool for modify the Store_Orders table as explained in my previous post, follow this:
Login to your web site as host. Then got to Host > SQL and paste this 3 lines in the text box:
DECLARE @OrderTable nvarchar(50)
SET @OrderTable = '{databaseOwner}{objectQualifier}Store_Orders'
DBCC CHECKIDENT(@OrderTable, RESEED, 2500)
Replace the number in bold red by your higher order number, check 'Run as Script' and click on 'Run'.
Gilles