OK, I've figured out that Part of the Problem was based in Kerrville, Texas. The band might be defunct; this web address: http://www.partoftheproblem.com/ used to belong to them but is now defunct and for sale. It can be seen via the Wayback Machine.

So far, I haven't found any confirmation—beyond the assertions of our 2 guests above—that they had anything to do with the parody BLUE HAIRS DRIVING IN MY LANE.

Two other bands, one from Waukesha, Wisconsin and another in Atlanta, have the same name, but I think that's coincidendal.