I know this is an old post, but completeness of this thread I would like to add the below comments.

DBA as well as Jeff.Mason was partially correct in the sense that normally by default primary keys are clustered. Eventhough it is not a requirement for a partition column NOT to be in the primary key, but best practice is for a partition column to be part of the clustered index. Without this, i.e. partition key not in the clustered index, and since in SQL Server, all indexes and data sitting on top of clustered index, SQL Engine will always perform a table-scan and not partition scan and hence creating a partition is not affective at all.

Cheers,

Fredy