I can only think it can happen if you are using the same sequence number for something else, like packing slip numbering, that goes together with invoicing…
If you are developer please check code once to be more specific if its a same number sequence.Or just try to change format to see if you are in right direction…