Hi Maggie,
There are a few things you could try, sadly you have probably exhausted online resources for the time being. The first place I would go is the catalogue of the National Records of Scotland. You can access it here:
http://catalogue.nrscotland.gov.uk/nrsonlinecatalogue/search.aspxTo begin I searched for Coldstream and Haliburton. There are four interesting results:
GD1/191/3, GD1/191/4, GD1/191/6 and GD267/26/13/251
All of them are very interesting and may help. The catalogue is very detailed for these items, giving a brief summary which is excellent.
GD1/191/4 is described as ‘Disposition by Patrick Halyburton [Haliburton], bailie and merchant in Edinburgh, to John Halyburton apothecary in Coldstream, and Isabell Sanderson, his spouse, of subjects in Charter of 26 Feb 1691’.
A look at the original document may give more in the way of relationships. Patrick is more than likely related to John, but how? The catalogue entry does not say.
The other entries are interesting too, definitely worth a look.
Before beginning any research in the National Records of Scotland (whether you go yourself, or pay a researcher) I would recommend buying their book ‘Tracing Your Scottish Ancestors: a guide to ancestry research in the National Records of Scotland and ScotlandsPeople’:
http://www.nrscotland.gov.uk/research/visit-us/shop It is available from various online retailers but make sure you get the up-to-date version.
If these entries show what they appear to show, that the Haliburtons were people of status living in Edinburgh, you will probably be able to trace your family tree back very successfully.
As well as these references there are other records such as sasines (land records) which will give more details, deeds, as well as tax records. On this occasion I would suggest starting with the references above. Also now you have some more details on the family you may be able to go back to the online resources such as the wills on ScotlandsPeople (which you can view for free in the NRS) and use them to trace your family too.
Hope this helps,
Emma