RPC Fails but passing in SQL Man. Studios works

Question

I am calling a stored procedure from a web service in an ASP.Net application. And until a few days ago, all was well. However now when i call it I get an error saying

The timeout period elapsed prior to the completion of the operation or the server could not be reached.

However when i would run SQL SERVER PROFILER, I could see that the call was getting to the database, but was timing out.

I then copied the statement being executed found at the bottom of the Profiler and pasted it into Management Studio and executed it and it finishes in about 7 seconds.. This runs just fine on our production server.

It seems to be similar to this question: SELECT DISTINCT not working in .NET application, but works in SQL Mgmt Studio but I see no answer.