I guess it is okay to answer your own question once in a while...
Inside the sales_flat_creditmemo table look for increment_id column and change the number to one increment above the current number. For example, the increment_id was 100003910 so I changed it to 100003911 and I can now create credit memos.
UPDATE Another even better approach would be to use the Fooman Order Number Customiser. I've added to help with the duplication of Order No. Shipment No. Invoice No. and Credit Memo across mulitple stores...