Sachverhalt: A. In der von der Y._ GmbH angestrengten Betreibung Nr. 1 des Betreibungsamtes C._ über Fr. 100'000.-- schlug A.X._ Recht vor und erhob die Einrede mangelnden neuen Vermögens. Mit Entscheid vom 17. Februar 2005 bewilligte der Amtsgerichtspräsident D._ von E._ den Rechtsvorschlag mangels neuen Vermögens im Umfang von Fr. 60'850.-- nicht und stellte die Betreibung für den darüber liegenden Betrag definitiv ein. Das Bundesgericht trat auf die dagegen erhobene staatsrechtliche Beschwerde am 13. Oktober 2005 nicht ein (Urteil 5P.117/2005). B. A.X._ reichte am 31. März 2005 beim Amtsgericht E._ gegen die Y._ GmbH eine Klage auf Feststellung ein, dass er vom 1. Mai 2003 bis 30. April 2004 kein neues Vermögen erworben habe. Demzufolge sei ihm der Rechtsvorschlag in der Betreibung Nr. 1 des Betreibungsamtes C._ vollumfänglich zu bewilligen und das Verfahren im gesamten Betrag endgültig einzustellen. Mit Urteil vom 25. Juli 2008 bewilligte das Amtsgericht E._ den Rechtsvorschlag mangels neuen Vermögens, soweit er den Betrag von Fr. 60'180.-- überstieg. In diesem Umfang wurde die Betreibung definitiv eingestellt. Das Obergericht des Kantons Luzern wies die von A.X._ erklärte Appellation am 13. Februar 2009 ab. C. A.X._ ist mit Beschwerde in Zivilsachen vom 27. März 2009 an das Bundesgericht gelangt. Er beantragt, das obergerichtliche Urteil aufzuheben und festzustellen, dass er in der Zeit vom 5. Mai 2003 bis 4. Mai 2004 kein neues Vermögen gebildet habe. Damit sei ihm der Rechtsvorschlag für den Betrag von Fr. 60'180.-- zu bewilligen und die Betreibung Nr. 1 des Betreibungsamtes C._ endgültig abzuschreiben. Eventualiter sei die Sache zu weiteren Abklärungen an die Vorinstanz zurückzuweisen. Die Y._ GmbH verlangt, auf die Beschwerde nicht einzutreten. Eventualiter sei sie abzuweisen. Das Obergericht beantragt die Beschwerde abzuweisen, soweit darauf einzutreten sei. Mit Verfügung vom 30. April 2009 hiess die Präsidentin der II. zivilrechtlichen Abteilung das Gesuch des Beschwerdeführers um Gewährung der aufschiebenden Wirkung gut. 