When are you seeing that message? When you go to renew from within CBSubs and click the PayPal button?

Checking their documentation it's due to the basket invoice not being unique. Within CBSubs > Settings > Display > Invoices did you change the settings under "Invoice numbering" the defaults guarantee a unique invoice number. The defaults are as follows.

Numbering of invoices: Single invoice number, assigned at ordering time (default)
Invoice number format: [PREFIX_TEXT][NUMBER]
Invoice title format: Invoice [INVOICENUMBER]
Reset next Invoice [NUMBER] to: (empty)
Increment each consecutive Invoice [NUMBER] by: 1

The proforma defaults are as follows.

Proforma Invoice number format: PR-[PREFIX_TEXT][GROWING_ID]
Proforma Invoice title format: Proforma Invoice [INVOICENUMBER]
Invoice number format: [PREFIX_TEXT][NUMBER]
Invoice title format: Invoice [INVOICENUMBER]
Reset next Invoice [NUMBER] to: (empty)
Increment each consecutive Invoice [NUMBER] by: 1

Below can be used to randomly generate a unique invoice each time.

Invoice title format: [PREFIX_TEXT][UNIQ_ID]

 So if I understand your message the only thing I have to change is the "Invoice title format" and set it to [PREFIX_TEXT][UNIQ_ID], right?

Correct, that would guarantee a completely unique id every single time.