From reading your post, it feels like the issue clears up after some time... is that true? Is there something specific that you're doing to force queries to work again the REST Admin application (i.e., restart ArcGIS for Server, recycle an IIS app pool, restart IIS, reboot the server, etc.) or does it seem to just fix itself randomly?
Are you positive that, prior to clicking the Query button in the REST Admin UI, the Start Time and End Time are empty or contain a valid value? The only way I could reproduce the behavior you're describing is to actually input a value of 0 into both fields. Otherwise, I'm able to query via the REST Admin application and the ArcGIS Server Manager application without issue.
[ATTACH=CONFIG]29782[/ATTACH]
In case the issue is related to something specific within your environment, please download, install, and run Fiddler while reproducing this behavior. Check to see if you are getting any errors when this occurs.