Common Serial Port Issues
Common issues that came immediately to mind:


Ground connection: you need a shared ground to get a usable communication, this gives very weird issues like the ones you describe
Unstable clock on either side: as UART has no clock sharing mechanism the clock must be fairly well defined and may not drift much. If you are running from an internal RC oscillator this might be a problem. Better use a resonator or oscillator.
Wrong signal levels: Make sure both sides are working with the same signal levels and you are not trying to feed a TTL signal to a RS232 port.
Polarity setting: define inactive high/low on both sides the same (normally you won't get anything useful if this is wrong)
Correct communication parameters otherwise: baudrate, number of bits, parity, number of stopbits, flowcontrol
RX / TX mixed up: Often the signals are called RX and TX for receive and transmit. It also often happens to just connect RX to RX, but it should be RX to TX (receive on one end is transmit on the other) (can also happen the other way round, depending on how people look at it, it's a mess)