AA sometimes not working

We have a fairly simple Automated Attendant system (3-4 menus, 2 levels). It were working perfectly fine for over a year now.

Sometimes however, and more often lately, our callers are complaining that they can not navigate in the AA menu, the system ignores their key presses.

What can I do to fix these, or where to begin diagnosing it?

I use a Digium TDM400P card with 2 BRI lines and Asterisk 1.4.11.