>Anyone have any good ideas when a user adds a new record to a table, that has the same primary/candidate key of a previously deleted record.

You can diversify your approach:
1. Use surrogate (sequentially increased) keys.
2. Recycle deleted records, i.e. if you hit deleted key, recall this record replacing values.
3. Completely eliminate this situation when you delete a record, i.e. shred all key field values to some values which will never exist in real records, e.g. change positive values to negative etc.