Performance Tuning for Huge Table (SQL Server 2008 R2)
Upgrade to SQL Server 2012 and use columnstores. They thrive in these requirements. Seriously, download the evaluation edition and give it a try. Drop all indexes, drop the clustered index, simply add a non-clustered columnstore index on all columns and give it a whirl. I've seen cases just like your that reduced the execution time to 2-3 seconds, mostly because of segment elimination kicking in. Some supplemental reads:


SQL Server Columnstore Performance Tuning
SQL Server Columnstore Index FAQ
Achieving Fast Parallel Columnstore Index Builds
Work Around Performance Issues for Columnstores Related to Strings
Use Outer Join with Columnstores and Still Get the Benefit of Batch Processing
Using Statistics with Columnstore Indexes