Here's a couple of other techniques you might want to try:
If you want it to look like it's driven on pavement after a slog through the mud, muddy the sides of the tires, and then re-blacken (or grayen) the treaded area that would be a bit cleaner from contact with the pavement. There would still be a lot of mud in the tread crevices, though.
Alternately, you could do a vehicle that has just left the road and still has fairly clean tire sidewalls, with mud or dirt just on the treaded section.
Whatever you do, good luck!