Do you have a dayjob?
They say that early mornig workouts on an empty stomach are the bee's knees for fat metabolism but for me, working out in the mornings would require setting an alarm to wake up around 5am so I could still get to work on time. That doesn't sound like fun, and life's too short to be a slave to your workout schedule - plus it's contraindicated with regards to the Paleo prescription for good, long sleeps with a natural wake-up. I work out in the evenings (not on an empty stomach) because I find it to be an infintely more enjoyable schedule. 5am is a terrible time to be anywhere except snuggled up in bed, if you ask me.