The date 1840 might be old enough to have Barbara searches
through Parish records. Two way os finding birth records
(pay website)you can search all Ireland members for the birth of a Barbara in all Ireland and with the name Nathaniel should have no problem. Only 4 counties are not members.
A copy of a church record will give you place/parish, mother and father's name as well as mother's maiden name.www.geneology.nationalarchives.ie
No Nathaniel in either the Tithe 1833 or in the Griffith Valuation 1847-1864 (Fermanagh 1862) There is however, many years between.
The British phone book for Fermanagh shows 5 Rutledges.