You shouldn't have to use you leg on the shifter to get into reverse.
IMO, if the cover was/is interfering it should never have left the tranny shop. If you paid to have it work right and it doesn't, tranny shop should fix it for you. Sounds as though you have ruled out the shifter. (I assume you were using the channel locks on shift tabs and not the fork flats.) Bring it with the trans assembled and show'em what'cha got.