Aly, you did your best to make things work out. But the people are right who say that the terrier instinct to hunt smaller animals is too strong in this case.
It's not all that unusual for some dogs to be absolutely unable to share a home with a cat. On our OzDogRescue site, there is an icon placed against some of the dogs which means that the dog should go to a home where there are no cats.