Things to consider with a bigger table
You mentioned that you have the table (technically clustered index) partitioned.  

Does your query use the clustered key(s) as part of the search predicate?  If not, you are going to get scans, as opposed to seeks, against the partitioned index.  

Do you have any nonclustered indexes?  Are they also partition-aligned?  

Have you investigated your query execution plan to see what is happening under the hood of your poorly performing query?

Could you post your DDL, sample data, and your query, so we can better help you?