The figure-8 knot is characteristically hard to untie after falls. What many climbers do is, once the knot is done, to come back with the end of the rope inside the last bight - this is a sort of Yosemite finish. It makes the knot easier to untie, since after removing the extra strand, a lot of room is left for the rope to be untied (picture here). Andy Kirkpatrick, in his book "1001 Climbing Tips", says that using a rock or an aid-climbing hammer to smash the knot can make it easier to untie, too.
My personal opinion is: a knot that is so hard to be untied is a bad knot. The figure-8 was OK when climbers very rarely fell, and ropes where made out of hemp and whatnot. Nowadays, with sport climbing and falls becoming so normal, the age of such antique knots has come to an end. The double bowline or, better yet, the end-bound single bowline (EBSB), are easy to tie and inspect and can be untied with minimum effort. I have used the EBSB for the past 3 years both in multipitch and sport climbing (convincing a dozen other climbers to use it in the meantime), and I'm extremely happy with it.