The default threshold value for red eye reduction in fspot is -15. This is a bit conservative. A better value is 20 (that’s plus 20). This value does a much better job of fixing the red eye, but the red-eye area must be selected closely - i.e. don’t try and select two eyes at once.
To set the threshold:
Open GNOME Configuration Editor. Then apps, f-spot, edit, redeye_threshold.