Did a restore via iTunes, it didn't fix the issue. Should I just wait for iOS 9 since it's right around the corner? That's about a month without the app store but I got all the apps I need right now so I think I'll be fine.
What's odd is that this just popped up in the past few days -- but I've had 8.4.1 since it was publicly released.