Are temporary tables stored locally or on the server. Leading on from that, do you have disk quotas enabled?

Have there been any changes to Group Policy lately?

Can you copy the data down from the server to a client and run from there? Has an incomplete restore been done - data looks OK, but isn't?

Just a few ideas,

Simon