It all depends on the chord structure underneath the vocals. Try staying "within the chord", but have the harmony stay one interval up or down from the lead. For example, if the lead is singing D-F#-A over a D major chord, have the harmony sing F#-A-D. Rotate as necessary for other chords in the sequence.
Try to follow the same direction most of the time, i.e. when the lead goes up an interval, have the harmony go up an interval, too. For accents, you can go different directions, too.
Keep poking at it and you'll find the right harmony line.
If you need inspiration for harmonies, I'd recommend listening to Bluegrass/Folk/Country vocals (really). Real Country and Western music, not the overproduced pop crud on the radio these days. No telling what the backup singers are going to do until they do it. More than Words by Extreme also does some interesting things with vocal harmonies. And of course, there ain't nothin' better than Mo'town girl groups for backup vocals in general. If you can find some 40's and 50's acapella doo-wop, you'll probably find something worth copying. Lots of inspirational material to pick from, if you so desire.