DaiB, rest assured that you were legally seperated. The other a/c was probably several miles away and at that distance a vertical seperation of a 1000ft will look as if at same level. Although there is no radar coverage there exists a very strict and long established procedure which you can read all about here:
http://avsim.com/geoffschool/airline...ntictracks.htm