Your code is very verbose.
Any reason why you are not using properties? http://msdn.microsoft.com/en-us/library/x9fsa0sw.aspx
You can also override Equals() or the == operator to make testing for equality much simpler http://msdn.microsoft.com/en-us/library/ms173147(v=vs.80).aspx
As for your problem: Are you sure the order of the arguments on this line is correct?
Person pSearch = new Person(firstName, lastName, State, ZipCode, PhoneNumber, Address, Age);
more stuff to read: