Actually, that's one of the main reasons why I go to the gym (keeps the mind sharp), and one reason I feel justified going during working hours. But I still don't "bill" for those hours - i.e. I don't consider these working hours.

Think of it this way: if you bill clients for hours while you are at the gym and if they find out, you could very plausibly be sued by the client for that money back. Very few people consider the gym "working."

If you really are more efficient during your working hours (according to my definition) because of what you do in your non-working hours, you can justify charging more for your working hours.