Have to second Dave's Dirty Devil idea. I've never seen anyone on my trips here, only on the way in. Seems we were in the Beaver? Creek side drainage last time out.
Another spot, although it's the other side of the state, is Dark Canyon. Huge drainage, I've done about ten trips there and every time was incredible! Very solitary and remote, route-finding skills are key here. Have you been in Upper Escalante, ie Upper Death Hollow, Pine Creek, etc?Or how about the Cedar Mesa area: Grand Gulch, Road Canyon, Bullet Canyon, Fish & Owl, etc? All kinds of trips possible in this area.
Here is a great resource: http://www.toddshikingguide.com/Hikes/Hikes.htm
Also, Will Reitveld lives in this area and I'm sure could really turn you on to some cool spots! Have a great trip!