Chromatic polynomials are typically calculated using a deletion-contraction recursion, which is a very lengthy and awkward procedure to perform. The problem of computing such polynomials (which are a specialization of the Tutte polynomial) is
$\#P$-hard in general, so one can not expect miracles of the "d-c" recursion, which I assume is the built-in method of Combinatorica.
Determinining whether a graph admits a
$k$-coloring is known to be
$k\geq 3$, but there exist various approximation algorithms for performing graph colorings that are somewhat optimal. In , Bonnie Berger and John Rompel developed an algorithm with a performance guarantee of
$O(n(log~log~n)^3/(log~n)^3)$ and Magnús Halldórsson improved this result to
$O(n(log~log~n)^2/(log~n)^3)$ in .
In 2009, a research group from New Zealand calculated the Tutte polynomial of the truncated icosahedron and, as their website explains, this took about one week to compute in a cluster of 150 computers . So yes, computing the chromatic polynomial (more generally Tutte polynomial) of large graphs can be a complete nightmare as you already experienced. This is probably why finding efficient coloring algorithms remains one of the most exciting open challenges in combinatorics and computer science.
I hope this helps!
 B. Berger and J. Rompel. A better performance guarantee for approximate graph coloring. Algorithmica, 1988.
 M. M. Halldórsson. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 1993.
 "Code for Computing Tutte Polynomials" (http://homepages.ecs.vuw.ac.nz/~djp/tutte/)