I guess I am confused here as you do not have to have an index to setup a relationship.  Did you happen to build your project between creating the index?  It is possible that you had just created the BO and not built the project so it could not be reflected to retrieve the fields so that a relationship could be setup.

I was setting up a new Child-Parent relationship in the Child-Parent Relationship editor. In the Foreign Key Field dropdown, no entries were appearing. Not knowing exactly what the problem was, I added an index to the foreign key (it did not have one prior to this)

When I went back to the Foreign Key Field dropdown, all the fields now appeared from the Business Object

My question is, is it a requirement (even though its obviosuly a very good idea) to have an index set on the Foreign Key Field. Other than this, I dont 'think' I changed anything else