Tried that. I'm one of Apple's Beta testers, and iTunes tells me I've already updated to 8.4 (even though it's just the Beta version). I'm pretty sure the problem is that I have the Beta. My wife's iPhone and iPad updated without issue. I assume a fix will be along in the next few days.
I had the same thing. You can get it to work OTA if you delete the beta profile from Settings > General > Profiles. Then restart the phone, and check for updates again. It should actually get past the 'update requested' this time and install. After that, be sure to reinstall your beta profile from the beta seed site.