From what you are describing about the user experience with the categories it might be possible that the query is just taking that long to execute and it times out. You can reset the timeout period in php with this code:
<?php set_time_limit(<number of seconds>); ?>
You would just enter the number of seconds that you want to let the script run for in there and test it out. If you put in a high enough value you should be able to determine if the query is just taking a long time to execute or if no results will ever be returned.