Я вижу, что пробелы переведены правильно, но ваше регулярное выражение должно пропустить +
import re
s = 'ABCDE : CE ; CUSTOMER : Account Number; New Sales'
re.sub('[^0-9a-zA-Z]+', '-', s)
Я на моем телефоне, но вставка в https://repl.it/languages/python3 дает мне
ABCDE-CE-CUSTOMER-Account-Number-New-Sales
как и положено - пробелы переведены.
Если вы хотите использовать несколько символов, потеряйте + в регулярном выражении:
import re
s = 'ABCDE : CE ; CUSTOMER : Account Number; New Sales'
re.sub('[^0-9a-zA-Z]', '-', s)
Дает
ABCDE---CE---CUSTOMER---Account-Number--New-Sales