[bobski]

Car horns throw out huge amounts of electrical noise in operation. They combine a big electromagnet with a set of contacts. When power is applied to the horn, it flows through the contacts to the electromagnet coil, which pulls on the contacts as well as the horn bell/diaphragm. When the coil has been powered long enough, the contacts are pulled open, which breaks the circuit. Momentum keeps the contacts open for a brief period, but spring tension eventually pulls the contacts and horn bell back to their original position, re-making the circuit and restarting the cycle. This happens several hundred times per second, producing the horn tone.
The electrical noise comes from arcing across the contacts as they open, as well as inductive flyback from the electromagnet coil.

Inductors (electromagnet coils) act like capacitors in that they store energy, but rather than trying to smooth out voltage, they try to smooth out current flow. If a charged capacitor is shorted, it will push as much current through the short as necessary to maintain capacitor voltage across the short, until the capacitor is discharged. Conversely, inductors will ramp the voltage up as high as is necessary to maintain the original level of current flow through a high resistance load, such as an opened set of contacts, until the inductor is discharged. This voltage spike is known as inductive flyback.

Anyway, to deal with the horn issue, you need to filter out that noise with a capacitor or something on the power input lines. I would put it on the car side of the voltage regulator.

The overheating regulator is a load issue. Regulators are spec'd to handle a certain amount of power dissipation (watts of heat); this number is generally higher with a heat sink.
[power dissipation in watts] = [voltage across the regulator in volts] * [current through the regulator in amps]
Voltage across the regulator should be supply voltage (car battery voltage) minus the regulator output voltage (5V). Since these voltage regulators are basically resistive elements, current through the regulator should be the same as the current drawn by your MPGuino circuit.
The real question here is what has changed to make the circuit overload the regulator. Unless your alternator is failing, we can reasonably assume that supply voltage and the regulator output voltage haven't changed, which only leaves an increase in current draw by the MPGuino circuit. I would poke around and see if any other components are heating up (drawing more power than they should). If not, go over everything with a magnifying glass hunting for shorts (stray wire strands, solder bridges and such).