This quest is Alliance only, but when you reach Gagetzan as Horde (via the Horde Breadcrumb To Gadgetzan You Go!) it pops up saying this breadcrumb is available. Basically, you need to switch the flag to Alliance only, as it is set a "both" currently.

Admitted a minor problem, when there are huge ones like all of TBC and WotLK not showing in the quest log, but still.