I understand that changing the timeout isn't a long term solution, but does it actually work? I.e.: If you change the timeout will the query succeed? I'm asking because if yes then we have a performance problem, if no it's even worse.
Could you please provide us with some more information? We need to try to reproduce the situation....