While the medallions are not cheap, remember that the OP picked up a cab in EWR. This is not a NYC cab we're talking about here. Different process and procedures in NJ and I have very often found gypsy cabs in EWR are ripoffs.

OP - next time, if there is one, you should settle this before you put your bags in the taxi. If they try to rip you off you simply ask for another cab. Just curious...did you stand in the normal taxi line at EWR or did you take the first person offering car services?

-RM