ESP8266 Returns 'invalid' - Cause 4
Alright so I figured it out. Thanks to user Butters for pointing me in the right direction.

The Arduino Uno DOES NOT have enough power to handle the ESP8266 itself. It needs a power source using a 5v to 3v stepdown chip. The 3v3 rail doesn't handle it by itself.