The point was that there were no bypass capacitors at all, and that clearly was the problem.
The proper place for the bypass capacitors is as explained, one directly across Vcc and ground for each chip. If you provided one across the power supply connection or the FTDI breakout and it made the system work, then you have halfway corrected it.
Yes Paul_B... I just realised how dumb was my comment... I was still thinking about the fact that you mentioned to physically add them on the back of the PCB.
This also answers my question about how to solve the problem in the future. So I guess it doesn't matter that I will be doubling these caps when I do connect the FTDI.
Jiggy-Ninja:
Too much capacitance on your power rails is basically never going to hurt anything.
Too much capacitance = large inrush current and/or slowly rising (and falling) voltage. But I agree it is much more difficult to have too much capacitance in common scenario.