Sorry for the test message above.
I just wanted to add my very similar experience w/ FireFox 19. I lost the icon completely, not even available anywhere even when in Customize mode. The option to check "show in addonbar" could not be selected. My solution was to Disable every addon except AdBlock Plus, restart Firefox, then finally I could check the "show in addonbar", and it would appear where
it always has been.
Unbelievably while typing this comment - the AdBlock Plus icon just disappeared - even after it had been working for over
an hour. I guess I will do the above steps again to get it back. It seems something is "overwriting" its ID if i had to guess.