We've been experiencing this SQL error with one of our sites lately. When I ran the offending stored procedure in SSMS, it ran in under a second. Running the page with this stored procedure would hang for 30 seconds and then time out.
The quick fix is to run the following:
DBCC DROPCLEANBUFFERS DBCC FREEPROCCACHE
This is just a temporary fix. I need to dig into the real issues behind these errors.