Strange power issue when using AltSoftSerial

Unsure if this is the right forum. I've built a project that involves using AltSoftSerial and an Arduino Uno.

My development has been over USB this whole time, and I recently printed a circuit board and soldered everything up. I was puzzled when I plugged in my power (9v -> 5v Regulator) and noticed the serial connection was printing garbage.

Turns out if I power the Arduino over USB it works fine, but when powering it at 9V from the barrel connector it starts to print garbage or nothing at all. This happens on my board as well funny enough.

Any ideas why this is happening? Code is being execute because the Blink example works fine while garbage is still output. Voltage seem fine to at 5v.

Edit: Tried the built in Serial as well. Wired a FTDI adapter to the TX pin and the same symptoms appear, so it's not specific to the library. Could the chip be faulty?