The Classic Timing Analyzer should be able to report Tsu/Th/Tco and min Tco constrants for each IO, even if you don't have them constrained. (The constraints tell the fitter to try and do a better job, and tell you if it passed or failed). In the end you'll need to determine what constraints you can handle.
1) It is strange that it starts working when you run it faster. Without knowing much about the situation, that often points to a hold violation.
2) With hold violations, you may need to do min timing analysis too. The standard timing model is worst case delays of the part at worst case PVT(process, voltage and temperature). The Fast timing model is the best case model for PVT. This analysis can be turned on under Assignments -> Settings -> Timing Analysis -> More Settings -> Enable Fast/Slow Analysis. Note that you don't have to change your constraints, as they are valid over the whole timing analysis range. This model basically let's you "complete the picture" as delays will fall within this range.
3) How come you have two clock cycles? If the ASRAM is completely asynchronous, you use one clock cycle to send address/control to it. Are you sending new address/control values every other clock cycle(thereby giving you two cycles)?
4) Can you take the reported delays and draw out your transfers, i.e. a clock edge sends data off chip, through the external memory, and back again to be latched by another clock edge. That's your setup path and you want to make sure the full path is quick enough to meet requirement. Also look at the min timing path, in that the fast model doesn't complete this path too quickly and corrupt the next data(this might occur if you thought you were giving yourself two clock cycles , but are sending addr/cmd on ever clock cycle, so that if the roundtrip occurs too fast it corrupts the previously send data.
5) Finally, you might have to do some debug, such as SignalTap, to see what's failing. If you know what you send out and what you expect to get back, it might be apparent pretty quickly if you're off a full cycle, if certain bits are getting captured incorrectly, etc.
I know this seems like a lot when it used to "just work", but understanding IO analysis is difficult and is one of the most important steps for a design. Designers who skip this step often ship things that work marginally. It allows you to be more confident in your designs and let's you move towards more demanding IO structures, where proper IO analysis is a must. Good luck.