Have you checked the shocks yet? If you wheel is becoming airborne after a bounce (whilst you're braking), that'd definitely cause your ABS system to be reacting as it has. When you replaced your tires, did you ask the technician if there were any strange wear patterns? A constantly bouncing wheel (which happens when your shock or strut is kaput) will wear unevenly and a good tire guy (or gal) can usually tell just by looking at it.

-Zeke