Nick, here's a link explaining parameter sniffing and how to work around it:

http://www.databasejournal.com/features/mssql/article.php/3841271/T-SQL-Best-Practices-150-Parameter-Sniffing.htm

It is probably worth trying to change your query so that you assign the parameters to internally defined variables and then use those internal variables in the rest of your query (as opposed to using the parameters directly).

HTH,

Rob