Have you tried a stiff brush on them? You might not even need a cleaner. If you do decide to go for a cleaner, make sure that it does not leave a slick residue on the tires, as many will. That could be bad news on the road until it wears off. I would think that something you could buy in the store for automotive tar/bug removal use might be all right on the tires, though I don't know how effective it would be. I'm used to using it mainly on painted surfaces when detailing cars. The product I use takes off the bugs/road debris very well with a hard surface behind it, but I would think that it would at least loosen some of it up on the tire. I would think that taking the bike out for an MTB ride over some rougher trails with roots/rocks would dislodge most of the tar from your tires. If not, try letting some air out of the tires to see if it will let you pick at the tar better. Check the label of any cleaner for a warning about use on rubber/a tendency to leave a slick residue.

-Moab