Why didn't you ask the electricians what exactly was the issue they found?
You have a right to know what you're $800 is going to be paying for.

I haven't had any direct contract with the electricians, only my general contractor. My general contractor said the wires were reversed in the outlets and that all the upstairs outlets had to be taken out and fixed and GFCIs installed. Can wires be reversed and the receptacle tester still indicate all is correct? Could my general contactor have misunderstood the problem? I had issues with the electrician's work during my basement renovation, So, I am more suspicious than I would typically be.

What does "fixed" mean I wonder... And does the GC know that a single GFCI receptacle (or breaker) can protect many things downstream?

Is there a bare or green ground wire in each box connected to the receptacle ground screw?

if you purchased a common tester that can detect reversed hot and neutral, as well as missing ground, you have covered most of your bases.

There are still things that can be wrong: Wrong size wire, poor workmanship, etc... but you should expect an explanation letting them know you tested for reversed wiring and missing ground.

Here is a link that might be useful: Simple tester

Asking your contact to put the nature of the faults and details of the remedies in writing would be a big step forward. It forces them to be organized. They will think again about putting fraud in writing rather than just speaking it.

Stanard "plug testers" can be fooled by a "bootleg ground".