Beavers Bend State Park in Oklahoma. It's about a three hour drive and on the border with Arkansas in the Ouchita Mountains. The Lower Mountain Fork River runs through there and has some great fly fishing for brown and rainbow trout.
Lost Maples has awesome camping. I've always done the primitive camping, so I can't speak for anything else... but if you're saying the primitive camping there isn't good then you've got ridiculous standards. Sure, it's not Colorado, Big Bend, etc, but for this region of Texas it rocks.
I just saw you listed Pedernales as good. I've done the primitive there 6 times and it is good, but to call that out as good and Lost Maples as not good it completely nuts.
to get the full appreciation of LMSP and even have a chance of hiking all the trails, you have to camp and spend a weekend there when the leaves are changing. in the fall, if you camp, you can hike one of the loops in the morning before they open the gates for the day-trippers.
i like the primitive camping at LMSP because the trails are well defined and camping sites well marked - which came in handy last Nov when the gf and i hiked in at night. Plus, most the sites are by water and have toilets - good for the gals. if you go during the spring/summer the crowds are not an issue.
I definitely agree about the weekend part. We used to get in on Friday (later afternoon or evening) and hike back out on Sunday afternoon.
The Mystic Canyon trail is pretty kick *** (especially in the fall)- and those loops have some nice views. The elevation for the one on the west side of the park is something like 2,200-2,300ft.