The quote from The Hunt for the Ring goes on to say that
...the Black Captain stayed there for some days, and the Barrow-wights were roused, and all things of evil spirit, hostile to Elves and Men, were on the watch with malice in the Old Forest and on the Barrow-downs.
Appendix B gives us a few relevant dates:
September 22nd: The Black Riders reach Sarn Ford at evening; they drive off the guard of Rangers.
September 23rd: Four Riders enter the Shire before dawn. The others pursue the Rangers eastward, and then return to watch the Greenway. A Black Rider comes to Hobbiton at nightfall.
September 28th: The Hobbits captured by a Barrow-wight.
September 30th: Gandalf reaches Bree at night.
The Hunt for the Ring also tells us that the Witch-king was at Sarn Ford during the skirmish:
Some dared to bar the ford, and held it while the day lasted, but at night the Lord of Morgul swept them away.
Since he was fighting the night of the 22nd, the earliest that he can reasonably be expected to visit the Barrow-downs would be on the 23rd, though it might be later if he was involved in chasing rangers or camped at Andreth for any significant amount of time.
After that, he spent "some days" in the downs, which I read as at least three. That puts his departure from the Barrows-downs no earlier than September 26th, two days before the Hobbits passed through.
But he easily could have stayed there longer. At the Council of Elrond, Gandalf had this to say:
'So I stayed there that night, wondering much what had become of the Riders; for only of two had there yet been any news in Bree, it seemed. But in the night we heard more. Five at least came from the west, and they threw down the gates and passed through Bree like a howling wind; and the Bree-folk are still shivering and expecting the end of the world. I got up before dawn and left after them.
'I do not know, but it seems clear to me that this is what happened. Their Captain remained in secret away south of Bree, while two rode ahead through the village, and four more invaded the Shire. But when these were foiled in Bree and at Crickhollow, they returned to their Captain with tidings, and so left the road unguarded for a while, except by their spies. The Captain then sent some eastward straight across country, and he himself with the rest rode along the Road in great wrath.
That puts the Witch-king in the area of the Barrow-downs or Andrath until September 30th, after the Hobbits' journey. Christopher Tolkien identifies the secret location with the camp at Footnote 22 of the Hunt for the Ring, which makes some sense. But the possibility is open that the Witch-king was in the Downs very close to the same time as Frodo.
