The army Belisarios commanded had a large hunnish contingent but was still majority "native" east roman troops.
I believe christianity played a part in the fall of the western empire, but there didn't seem to be a problem of getting christians to fight in the army. Though I could be wrong.
The eastern empire used barbarians but, as far as I know, not to such an extent as the western empire. Another subtle difference, is the eastern empire deployed its forces slightly differently than the west. The eastern empire kept the majority of its troops as border soldiers (limitanei) versus the west which had a majority of comitatus (mobile field armies in the rear), some believe this is a reason for the wests' collapse and the easts' survival. The east was also wealthier than the west. Another point is the east could apparently recruit more native soldiers than the west, the balkans and anatolia were apparently more willing to join the army and fight well than say the iberian peninsula. The eastern capital (constantinople) was also much easier to defend than rome, though the de facto western capital was Ravenna, which was also very difficult to take. Also, the east was hit first by nomadic incursions, the east being wealthier could simply pay off the barbarians and make a stand, if the eastern empire could bribe off the nomads or put up a fight the nomads would simply head to the west and invade the western empire. So you could say the western empire had a much more difficult time in defending itself, less wealth and arguably more enemies.