Theodoric was not going to suffer this insult quietly or let his people starve, so he invaded communities in the Rhodope Mountains in southeastern Europe (Bulgaria), slaughtering peasants and taking supplies. Their savagery drew an attempt from Zeno to make a truce, but Theodoric was not satisfied. He sent an emissary to Zeno, who was in Epidaurum at the time.* Meanwhile, Zeno sent soldiers to attack Theodoric's people, stealing (supposedly) 2000 wagons of supplies and capturing 5000 Ostrogoths.
Zeno made many bad political decisions—including losing the Western Roman Empire—and in 483 he offered Theodoric the position of absolute top military commander and made him consul in 484. Consuls were the chief magistrates of the Roman Republic. This position did not mean hostilities ended between Theodoric and Zeno. Theodoric continued to plunder Eastern Empire territories, approaching Constantinople itself.
Zeno engaged the Bulgars to attack Theodoric; the Bulgars were defeated. Theodoric besieged Constantinople, hoping to pressure Zeno into giving him land for the Ostrogoths. Zeno was having trouble with Odoacer, the Germanic ruler who was king of Italy, and offered Theodoric to defeat Odoacer and take Italy. Theodoric initially lost against Odoacer in 490; the two rulers spent the next few years fighting across Italy, finally negotiating a co-ruler treaty to stop the hostilities.
One of the two never intended to honor the treaty. I'll tell you which one next time.
*Epidaurum would be devastated two centuries later by Avar and Slavic invaders; citizens would flee north several miles and found a new city, Ragusa.