Did the same thing with my shop floor when I first moved in 6 years ago. Spent 5 days cleaning (with Tide and Simple Green), etching, drying, and prepping the floor for an industrial epoxy paint. Laid it down like butter and let it dry for a week.
A couple weeks later I drove my Z into into the shop after a day of autocrossing and the sticky Hoosier A3s peeled the paint right up in 9" wide strips.
I will never, ever paint or epoxy a concrete floor unless its brand new concrete. Even then I'll probably use a stain instead of a paint or epoxy.
http://www.concretenetwork.com/stained-concrete/