I'd be curious to see your source for Pharnabzos ruling Cilicia at any point. I'm not familiar with that claim and I'm not seeing it in any of my easily accessible online sources. Pharnabzos (specifically Pharnabazos II) was Satrap of Hellespontine Phrygia, and for most of his later life he was the senior satrap in Anatolia. That put him in command of the Persian military in the west. As the senior military commander, he interacted with Cilicia a few times because it was Persia's primary naval hub in the Mediterranean. However, his actual seat of power in Dascyleium was on the northern side of the Anatolian peninsula, near the Sea of Marmara. In between, there was an independent satrapy in the form of Lydia.

Meanwhile, Datames' relationship to Cilicia is only marginally clearer. In rare twist for Persian historical figures, Datames is actually known primarily through a biography written by the Roman biographer Cornelius Nepos. Nepos reports that Datames' father was the governor of "Cilicia Near Cappadocia" and that Datames himself inherited the position when his father was killed as part of Artaxerxes II's Cadusian Campaign in the mid 480s. However, Nepos does not address when Datames' role expanded or shifted to become Satrap of Cappadocia itself. As Nepos' narrative continues, Datames just is a significant Satrap all of a sudden.

There's a few plausible explanations here. The name "Cilicia Near Cappadocia" only appears in this context. It's possible that it's a mistake caused by Nepos' own attempt to reconcile competing information about Datames' office. However, it's also possible that Cilicia was split after the deposition of the last Syennesis. The Persian administrative divisions were never static. Border regions shifted between provinces as inter-satrap politics changed. Moments of military realignment or rebellion were both common causes, and both were playing out in the western empire during the early 4th Century. In that case, there may have been a region of Cilicia "Near Cappadocia" as well as "Near Lydia" or something like that.

However, if you're encountering this question through numismatics, then you're probably running into the debate over the silver staters both Pharnabzus and Datames minted in Tarsus. A hoard of coins from both Satraps was found, leading to some confusion about why both were in circulation in large numbers at the same time. This article by Robert A. Moysey provides a reasonable explanation. Much of the Satrap-issued coinage in the Persian west is believed to have been minted as pay for mercenaries or bribes for Greek poleis. The most relevant event involving a substantial number of Greeks in Cilicia during the 370s BCE would be Artaxerxes II's failed attempts to reconquer Egypt.

This provides a convenient framework. As Moysey points out, one of the designs minted by both Satraps seems to have been a stylized hoplite or image of the god Ares on the reverse side. The extant coins show that only two dies were ever used to produce this image, and that all of Pharnabazus' coins were produced using the first iteration. Eventually that die started to wear and crack, and all of Datames' coins using that die were produced in the damaged state, before switching over to a second copy of the same image. That would suggest that Pharnabazus minted coins in his own name first, and then Datames took that authority immediately afterward.

The best explanation for this chronology comes from Nepos, who says that Datames was promoted to overall commander of the Persian war against Egypt when Pharnabazus was recalled to court. From Egyptian records, we can guess that this was probably after a significant Persian defeat in 373. So neither of them was really minting coinage as governor of Cilicia. Instead, they took over the local mint as part of their military authority, which both had received by virtue of being the highest ranking satrap in the region.

The problem with dating Datames' rebellion, and the so-called Great Satraps' Revolt that spun out of those events, is a recurring issue in Persian history. Unless the specific events are referenced with a date, we have to rely on inference and context to establish a possible date range by comparing the event in question with other events on a better established timeline. Nepos doesn't provide dates in his Life of Datames. Diodorus Siculus places the all of the Satraps' revolts in the context of

When Molon was archon at Athens, in Rome there were elected as consuls Lucius Genucius and Quintus Servilius.

That means 362/1 BCE. Unfortunately, that section is placed immediately after a section describing the Corinthian War in Greece in 367, so there's not much context for the intervening years to help us establish things. Diodorus also had a habit of condensing Persian events together, so we can't take his dates entirely at face value. Every other source makes it pretty apparent that the Satraps of Anatolia were in rebellion for several years.

372 is probably not realistic for Datames' revolt. After taking control of the Egyptian expeditionary force and retreating back into Phoenicia and Cilicia in 373, Datames had one more legitimate assignment according to Nepos. After retreating from Egypt, and presumably returning to Cilicia to mint those coins, Datames prepared to go back on the offensive in Egypt, but got orders from crown. A revolt had broken out in Cataonia, an inland plain north of the Taurus Mountains and Datames needed to stop it. Datames moved quickly and had already handled the revolt quickly and became a favorite of the king.

According to Nepos, he was warned that jealous nobles back in the royal court were conspiring to have him executed if the Egyptian expedition failed. Whether that's true, or if it was simply the precedent set by Pharnabazos' failure is debatable. Either way, Datames was already in Acre on his way back to Egypt when he got this warning and decided to leave the expedition's camp and return to his satrapy to raise a revolt.

So the earliest possible date for that is 371, with 370 or later a bit more likely (372 to rebuild the army but 371 on campaign in Cataonia and no forward progress until the next year). Between Nepos and the Roman military historian Polyaenus' Strategems, Datames is credited with at least four geographically distinct campaigns between the start of his revolt and his defeated in 362. Those would likely be separate campaign seasons, and Nepos does establish that he didn't campaign in the winter. So that gives a start date between 370-368 BCE.

If 6-8 years still sounds like a long time for a revolt, it's worth remembering that Datames' was not alone in his rebellion. Several other parts of Anatolia revolted at the same time, including Pharnabazus' son up in Phrygia and the governors of the sub-provinces of Caria, Lycia, and Mysia. According to Diodorus' potentially exaggerated account, the entire western seaboard went into revolt from Ionia down to Phoenicia. There's not much evidence for the southern regions, but given that an army most recently commanded by Datames was still stationed there, it is not unbelievable. It was an atmosphere ideal for holding out in rebellion for a few years.