It actually was, just NJ and NY weren't states yet.
Between 1664 and 1668 the history is a little fuzzy and conflicted. Most sources agree that SI has never been part of NJ. Although one source did say they paid taxes to NJ. I particularly liked this passage from the Staten Island Explorer by Andrew Stepanov.
"In 1664, an English fleet sailed into New York Harbor and captured New Amsterdam without a fight. King Charles II of England granted the colony to his brother James, the Duke of York, who renamed it after himself. The Duke of York also claimed all of New Netherland as his own, including Staten Island and New Jersey.
However, the Duke of York had a problem: he had already given away part of his land to two of his friends, Sir George Carteret and John Berkeley. In 1664, before he knew he would inherit New Netherland from his brother, he had granted them a large tract of land between the Hudson and Delaware rivers, which they named New Jersey after Carteret’s ancestral home. The Duke of York did not want to take back his gift, but he also did not want to lose control over Staten Island and other strategic locations.
To solve this dilemma, the Duke of York made a deal with Carteret and Berkeley: he would let them keep most of New Jersey, but he would retain some parts of it for himself. These parts included Staten Island, Long Island, and several other islands in New York Harbor and the Hudson River. He also kept a narrow strip of land on the west bank of the Hudson River opposite Manhattan, which became known as Bergen County."
But, in conclusion I'd have to say their is a grain in truth to the myth, for during a brief point of time both tracts of land were part of the same unincorporated Crown Colony when the English took it from the Dutch.
