There can be subtleties with the PC connection, for example when it's opened, it usually generates a reset pulse. It also may be invisibly depending on receiving or not receiving characters from the PC. Just some ideas.
I once had some Uno's (clones) that worked fine until attached to a wall adapter, so very similar thing. In that case, it turned out that the board reset was not working. So I added a 10uF cap to the reset line from ground and it worked from then on!