From a financial control point of view being able to delete and reuse invoice numbers damages your audit trail and leaves you open to risk. Also from a database integrity point of view, reusing primary keys is not allowed as it would lead to unexpected results,such as records in other tables appearing wrongly in a join. There are consequences to naturalising your primary keys (excellent discussion of natural and surrogate primary keys). The database is protecting its referential integrity by not allowing the reuse of the primary key. Indeed, as @David says in his response, part of the function of autoincrement on a primary key is to maintain the uniqueness of the key.
Now to solutions, from a financial aspect invoices should never be deleted so there is an audit trail, an incorrect invoice should have a contra through a credit note. On the database side if you must 'delete' a record and reuse the invoice number, I would suggest having a different field for the invoice number, not actually deleting, but using a field to flag active or deleted, and maintaining a separate incrementing invoice number. Although not advised, this will at least help maintain the integrity of your records.