Do you have an automated maintenance plan to update statistics, rebuild indexes, etc.? If not, SQL Server may still be building its query plans on your older statistics of smaller tables.
SQL Server generates parallel query plans automatically, if certain conditions are met. From an article on MSDN:
1.Is SQL Server running on a computer with more than one microprocessor or
CPU, such as a symmetric
multiprocessing computer (SMP)? Only
computers with more than one CPU can
use parallel queries.
2.What is the number of concurrent users active on the SQL Server
installation at this moment? SQL
Server monitors CPU usage and adjusts
the degree of parallelism at the query
startup time. Lower degrees of
parallelism are chosen if CPU usage is
high.
3.Is there sufficient memory available for parallel query execution? Each
query requires a certain amount of
memory to execute. Executing a
parallel query requires more memory
than a nonparallel query. The amount
of memory required for executing a
parallel query increases with the
degree of parallelism. If the memory
requirement of the parallel plan for a
given degree of parallelism cannot be
satisfied, SQL Server decreases the
degree of parallelism automatically or
completely abandons the parallel plan
for the query in the given workload
context and executes the serial plan.
4.What is the type of query executed? Queries heavily consuming CPU cycles
are the best candidates for a parallel
query. For example, joins of large
tables, substantial aggregations, and
sorting of large result sets are good
candidates. Simple queries, often
found in transaction processing
applications, find the additional
coordination required to execute a
query in parallel outweigh the
potential performance boost. To
distinguish between queries that
benefit from parallelism and those
that do not benefit, SQL Server
compares the estimated cost of
executing the query with the cost
threshold for parallelism value.
Although not recommended, users can
change the default value of 5 using
sp_configure.
5.Is there a sufficient amount of rows processed in the given stream? If the
query optimizer determines the number
of rows in a stream is too low, it
does not introduce exchange operators
to distribute the stream.
Consequently, the operators in this
stream are executed serially.
Executing the operators in a serial
plan avoids scenarios when the
startup, distribution, and
coordination cost exceeds the gains
achieved by parallel operator
execution.
Other factors:
Is SQL Server configured to have affinity to a single processor?
Is the max degree of parallelism option is set to 1?
-- EDIT --
Have you tried profiling this process? It would be interesting to see the query plan SQL Server generates.
Do you have sample code you can post?
If you have an automated nightly backup job, can you simply restore the backup to the archive?