Check the part number on the new relay.

Unusual that it should start right after service...

Its possible that you have the wires confused on the new radio - power wire connected to the 'lighting' wire?

__________________
1991 300 SEL
218,000 Km

"Xsbank's rules of mechanical intervention: Always go for the easiest solution first; 90% of what ails a gasoline engine is ignition; After that its all a WAG."