The short answer is that, in principle, they all continued to serve the Roman empire. The longer answer is more complicated and I'll only discuss the consulship here, as I definitely don't know enough about how the Roman or the Constantinopolitan senate worked.

The first thing to note is that what happened in 476 to the western Roman empire was not the end of an era. Instead, one ambitious general, Odoacer, had enough of his boss and decided to overthrow a puppet emperor. Afterwards, he then submitted (in theory) to the more legitimate but previously overthrown emperor, Julius Nepos, based in Dalmatia. After Nepos' death, Odoacer then did the same to Zeno ruling in Constantinople. The Roman order was not overthrown, as people instead acknowledged what was already self-evident - the western empire had been crumbling for years and repeatedly needed to be helped by eastern armies. Now that its territories were restricted to Italy, what was the point of needing a separate emperor? Moreover, there had already been long interregnums between western emperors, such as the ~19 months gap between the emperors Libius Severus (461-465) and Anthemius (467-472), so the lack of an emperor in the west in 476 would not have surprised the Romans.

As Odoacer had no need to tear down the Roman empire, he naturally continued to appoint consuls in the normal fashion - one candidate chosen by him, the other appointed by Constantinople. Occasionally there were years when no western consuls were appointed, but the same was however also true in the still healthy eastern Roman empire. By then, the consulship was a purely honorary position with only the responsibility of throwing circus games for the masses. Real power was held by the masters of soldiers and the dukes for military matters, and the praetorian prefects for civilian matters, so the consulship became only the preserve of wealthy aristocrats willing to put on a good show and perhaps use it as a springboard for a career beyond the consulship. If there were no rich nobles to desire the office, or if the emperor wanted to gain the adoration of the crowds by holding games himself, then there was no need to appoint someone to the office. In fact, the eastern empire began to offer 'honorary consulships' to those willing to pay in the late fifth century, so for many it must have seemed a bit pointless to spend more of their own money to gain the same title. The 'ordinary consulships' still had meaning however, as documents continued to be dated using the traditional formula of 'in the consulships of X and Y...' This was still true in the seventh century, even in the 'barbarian' lands of the Burgundians, so if you were an aristocrat and wanted a shot at immortality, getting the consulship was still worthwhile.

The same continued into the reign of Theodoric the Great, who led the Ostrogoths into Italy and murdered Odoacer in 493. Theodoric himself was once a consul of Constantinople, so it is natural that he continued to appoint consuls for the west. There were years when he was in conflict with Constantinople however, so in those years western appointees were not recognised by the east. In 508, the emperor Anastasius even decided to grant an 'honorary consulship' to King Clovis of the Franks as a reward for his campaign against the Visigoths in southern Gaul, which drew away Theodoric's attention even as the Roman navy began to operate against Italy. When the relationship between the two powers was more cordial however, western consuls were recognised and honoured, which is perhaps best seen in the consulship of Eutharic, Theodoric's chosen heir, in 519, as he was also acclaimed as Emperor Justin I's 'son-in-arms'. The last western/Ostrogothic appointee, Paulinus, became the consul in 533; after that, the Ostrogothic kingdom became embroiled in dynastic infighting (so appointing someone to be the consul was probably a long way down their list of priorities), which in turn provoked Emperor Justinian I's invasion of Italy in 535. By 541 the forces of Constantinople were seemingly triumphant, so Justinian appointed a western aristocrat, Basilius, as the western consul. He however did not know that the Gothic War would rage on for another 13 years, by which time Italy was devastated, exhausting the wealth of the traditional elite and thus the candidate pool for the consulship.

There was also another reason for the lack of consuls at this point. Justinian was an emperor with many enemies and so didn't appoint many consuls for the east anyway, as they would have used their new-found influence to gain support amongst the masses. The extraordinary victories of Belisarius in North Africa in 533-4 did result in the general's appointment as the consul in 535, an event that was celebrated lavishly. Soon however laws were issued to limit the spending of consuls and to end the subsidies given to eastern consuls to hold their games, no doubt because the cautious emperor had noticed that Belisarius was getting a bit too popular for his liking. This practice however had ended by 541, with the last consuls being the aforementioned Basilius and Justinian himself. As Alan Cameron has pointed out, the state was haemorrhaging money after this point due to the emperor's wars and the devastating impact of the plague, whilst previous consuls like Belisarius and John the Cappadocian were repeatedly linked to intrigues against Justinian. By then, there was no need for the consulship and probably no money for it either; even Justinian did not take the consulship for himself again. In Cameron's words:

If the emperor could not afford to be consul, it was clear that no one else could be allowed to.

The consulship was however revived in 566 by Justin II, a new emperor who wished to separate himself from Justinian's troubled legacy, especially the military and theological problems during the previous emperor's old age. However, from now on the consulship would be only the prerogative of the emperor, though even then they did not hold the office every year. This continued all the way to down to the reign of Constantine IV (668-685), though there is no direct evidence of him actually taking the office - the only evidence is his usage of post-consular years in his dating formulas, so presumably he, like his predecessors, also became the consul when he became the senior emperor.

There is something else to discuss as well, the 'consular' rebellion of Heraclius in 608, which was probably the last time someone used the idea of the consulship to bolster their political legitimacy. Heraclius, the governor of North Africa, had in that year revolted against the emperor Phocas and minted coins that depicted both he and his son, also a Heraclius, as wearing consular robes and with the inscription 'dominus noster Heraclius consul' - our lord Heraclius the consul. This was of course purely propaganda, since by then only emperors could be consuls, but it was no doubt part of the two Heraclii's strategy to draw on ancient Roman traditions to strengthen their rebellion's cause. It is a fitting end to the long history of the Roman consulship, as the younger Heraclius, the last non-imperial consul (albeit a self-proclaimed one), sailed from Carthage in the western half of the empire in order to seize power in Constantinople, which he achieved in 610, a bold move characteristic of the legendary consuls of old. Not too shabby for an office most people would have thought to have died out after 476, the year when Rome allegedly 'fell'!