A EP4CE55 has almost 4 times the resources of a EP3C16, all of which are powered from VCCINT. Whilst you may not be using all of them, and the power consumed by Cyclone IV is (generally) lower that of Cyclone III, the current consumed by your new part is likely to be higher.
If the supplies are clean - great. Do they remain clean having left the board powered for a significant amount of time with the FPGAs configured?
As well as filling out the power estimators, remove the output inductors you have on your VCCINT rail and connect up and power your board from a bench supply. That will give you an accurate reading for the current consumed by VCCINT. You will need headroom on this measurement as the bench supply will only give you an average reading. The voltage regulator will be able to supply peak current surges - the FPGA is likely to do this regularly. The decoupling you have looks sufficient. However, if the current is anywhere near the 250mA limit for that channel of the voltage regulator, I'd be concerned.
Could a problem on VCCINT cause JTAG problems? Yes, absolutely. The VCCA rail will only power the JTAG I/O, not any JTAG logic. That is all powered from VCCINT.
Having said all that, if the regulator isn't up to it, the voltage is simply likely to drop causing the FPGA to stop working. It's (perhaps) unlikely to damage the FPGA.
I'm more concerned about the short you have between VCCIO and GND. This almost certainly will be the result of one or more I/O pins being over-stressed, over-driven. Alternatively, but less likely given the power solution you have, the regulator supplying VCCIO for that rail has over-driven the VCCIO pins. Re-check all the signals going into the VCCIO bank that's failed.
Finally, do you have the same fault on multiple boards?
Cheers,
Alex