6x8 and 5x7 do not drop in the rear of a Protege5, however they will fit in the rear of a Mazda3. Given enough time and effort you can fit just about any speaker in any door, but if you are looking for "drop-in" replacements for your Protege5, stick with 5x7/6x8 for the front and 5.25/6/6.5 for the rear.
And for the record, the people at Best Buy get on-the-job training. If you value your vehicle, do the installation yourself instead of taking it to them. They have experience tearing apart early 90's Honda Civics in their friend's driveway but not much else.
...and also for the record. If you select a Mazda Protege5 on Crutchfield's site, they will limit your rear speaker selection to 5.25, 6, and 6.5 inch speakers.