Last I heard he just landed a morning gig in Texas.
The timing was strange when he left because the Cledus morning show wasn't on the air that long on the Bull, amd he also just got back from a road trip with Cledus to do a bit part in Toby Keith's movie "Beer for my Horses", and then all of a sudden he was gone. The weird thing is that the intro to the show had Paul's name still on it weeks, maybe even a month after he left.
I ever heard anything mentioned on the air about him leaving, but then again, you rarely do.