Yes, a UART is sensitive to frequency. Having as much as 1/2 bit of error at the end of a 10-bit character would be disaster. That's 5% variation.
There are gazillions of circuits out on the web. A 74LS04 is a good choice, as is a 74HCU04 (note the 'U'). A 74HC04 is _not_.
Define "garbage". As long as the overshoot isn't greater than 10% or so of the total then you should be fine, and depending on the shape even larger overshoots should be OK.
How are you measuring this waveform? It sounds like you're driving some pretty long pieces of wire to make things so sensitive to external influences, or you're powering the thing with long wire runs without any bypass caps. Have you looked at your VCC line to the chip? Is it bouncing around? Are you clipping your scope negative probe onto the chip's negative lead? Did you check the connection of your scope's negative probe to make sure it's still good?