They amended the claims which required the examiner to do another search.
As mentioned above, Final Rejection just means you have to pay more money to continue the patent prosecution. This is called a Request for Continued Examination. RCEs are common.
Generally, the initial filing fees provide for two rounds of examination -- a non-final rejection and then a final rejection.
If the applicant re-filed the same claims that were rejected in the final rejection (w/o amending them), the examiner can issue an immediate final rejection on a subsequent RCE if he disagrees with the argument the applicant might have supplied.