UART not functioning on power reset but ok on flash/fuse read

I have built a simple design using an ATMega328p design which talks to another sensor via the hardware UART data while reporting its findings using the SoftwareSerial library through a Bluetooth module from Sparkfun. I'm flashing my design through AVR Studio using the hex file created via the Arduino IDE and the AVR MKII ISP.

Fuses are set up as E2:DF:FF

When I first flash the program to the device, it works as expected. I get data coming through the UART (via function) and going out the Bluetooth module via the SoftwareSerial library. If I read the fuses, which essentially resets the device, it again works as prescribed. If I flash the design, power it off, remove the AVR MKII ISP and repower it up, it works as prescribed.

The odd part is, if I cycle power again, regardless of whether the AVR MKII ISP is hooked up or not, I get no data coming in from the UART even though my logic analyzer verifies that the sensor is sending data. The SoftwareSerial library works perfectly going through the bluetooth module all the time. At this point, with the UART not working, I can either just check the fuses again through the AVR Studio tools, and it will start to function properly, even without a power cycle or just reflash it and it will work perfectly until the power is cycled again.

I'm stumped. Something is different compare to when the device is programmed/fuses check versus a power cycle that is enabling the UART to work properly.

I'm compiling on Arduino v1.05-r2.

Thanks in advance