I have seen this exact issue in my own design and it stumped me for a while, but the problem turned out to be a lack of timing constraints on the JTAG clock and the design fails setup & hold within the SignalTap instances.
All the pieces seemed to make sense when I thought about it.
The device would program just fine because the JTAG signals only connects to the hard programming logic at power on. After programming it with a badly-P&R'ed SignalTap instance, which the JTAG signals are now routed into, the JTAG data nets would be failing setup & hold inside the fabric of the SignalTap instance, and any data returning from those instances would then be metastable or just plain wrong. The returned data would take on a random form, also corrupting any JTAG control messages along with any collected data, which explains the variety of error messages you can see in the SignalTap window. I saw maybe 4 or 5 different errors if I repeatedly clicked the Run Instance button.
This also ties in with your observation that reducing the JTAG clock rate fixed the problem, as the P&R engine would find it easier to make a valid fit on a poorly constrained design if the clock speed was reduced. You may find that the exact same P&R that fails at 24MHz works fine at 6MHz (you could test this by constraining the P&R to post-fit and then changing the timing constraints to reduce the TCK clock rate in the Static Timing Analysis tool ie. TimeQuest, and see it suddenly meet S&H).
I think a basic SDC constraints file should fix the problem, assuming you don't have one already? Or maybe there are some errors in it. At least tinkering with this for me solved the problem.
First check for clocks that are failing S&H using TimeQuest (if you haven't used TQ much there are some basic tutorials around but the tool is very powerful. The following document from the Forum User 'rysc' is a great place to start, with the first chapter being a great introduction to the most important commands.
http://www.alteraforum.com/alterawiki.com/uploads/3/3f/timequest_user_guide.pdf)
Use the 'Report All Summaries' macro and then see if any clocks are failing Setup or Hold. The JTAG clock is called 'altera_reserved_tck' by default. Mine was failing on Setup.
A basic SDC file with the commands 'create_clock', 'derive_pll_clocks', 'derive_clock_uncertainty' and 'set_clock_groups' is probably all that is required. Use TQ to copy out all the derived pll clocks and paste them into the 'set_clock_groups' arguments. Above linked doc also describes this step.
And that fixed it for me.
Hope this helps, but I am far from an expert, so maybe I overlooked something obvious.