If it were my design, I would use AD7708 and a separate temperature sensor on the PCB for ice point compensation.
Since 50/60Hz is a common mode signal on both TC lines, it's canceled by a differential amplifier (in the front end or in the integrated A/D). RC filters reduce higher frequency noise, which can be rectified by the amplifier, which would cause an offset in TC reading. Depending on the amount of noise in your environment, this may or may not be a problem.
The approach with an external mux is viable to. Check that the mux doesn't inject too much noise. A mechanical relay would be a really low noise mux.
edit: On floating thermocouples vs. common leads.
The topology with a common TC lead could work. But there are caveats. Different TCs can be a slightly different potential (common mode). If there is a shared lead, a current may be flowing through it, which can skew reading. If thermocouples are spread around spatially, they may see different noise. The noises will be added on the common lead, but will appear separately on the separate leads. 50/60Hz noise cancellation would not be as good.
update: Related post on floating vs. grounded thermocouples.
An accuracy of +/- 5°C accuracy at 280°C amounts to about 1.8% error. This results in an effective resolution of 6 bits (assuming the full measurement range would end at about 280°C). 10 bits of resolution would result in about +/- 0.28°C accuracy, and 8 bits in about +/- 1°C. So you don't need to worry here (Even when you are not using the full range of the ADC input).
The easiest solution for your overflow problem could be to use Avcc as reference voltage (but then it should be noise-free, precise and stable enough). This reduces your resolution (by half when compared to the internal reference, because it doubles the measurement range), but you have plenty of room there (you use about one fourth of the ADCs input range then, so you get 8 bits of effective resolution over your temperature range).
If you want to improve resolution, use a 3.3V low-noise regulator to create both Vref for the AVR, and Vcc for the AD8459 (it can run with this voltage). That way you can be sure the voltage from the thermocouple amplifier never exceeds the reference voltage.
But you also can use a zener diode to clamp the voltage of the amplifier. When looking at e.g. the ATMega16 data sheet (you did not specify which AVR you use) it has an input resistance am 100MOhm, and states that an input impedance of less than 100kOhm is suggested. So the clamping will not have any effect as long as R1 in the schematic above is small enough. And 10kOhm would be perfectly OK - the amplifier then needs to source 0.5mA.
Using an external ADC is another solution. If you can afford the board space and the additional components, it seems even like the best solution. Look for an ADC with a reference of 2V which also can stand inputs up to its Vcc, then you are fine.
I personally would go with the 3.3V LDO solution. You might need a stable and noise-free reference voltage anyway, so why not using it to solve other problems as well?
Best Answer
You'll need to amplify the signal to the range your A/D can handle - there are existing parts for just this purpose. F/ex, Analog Devices' AD595 thermocouple amplifier. Simplecircuitboards.com sells boards based on it.
For a more comprehensive solution, Maxim MAX6675 is a complete thermocouple conversion device (thermocouple in, digital out). It's currently in "Not Recommended for New Designs" status by the manufacturer and I didn't see a recommended replacement but that may not matter if you're not designing it into a new product. Adafruit Industries sells the part on a breakout board ready to plug into a breadboard.