Проверьте, во время работы, на разных скоростях, разность напряжений на коммутирующих выводах релюхи, сравните с её номиналом, если не превышает, то поставьте последовательную RC-цепь, что-нить вроде 100ом+10...100нФ, можно добавить плюс к этому варистор, возможно просто нужно искрогашение...
А там, где-нить нет случайно реле общего отключения вентилятора? может оно в момент переключения должно размыкаться?
"Плавающее" к.з. в проводах?
Ну и самый неприятный вариант - неисправность в логике переключения скоростей, например, не выдерживается пауза между отключением одной скорости и включением другой...