AFAIK you can get tri-band phones from Siemens (S40), Nokia (8890) and the Ericsson. I bought a Siemens in Hong Kong for USD 500. I think the Nokia is a fraction more expensive (also lighter and funkier looking). Haven't seen the Ericsson, but can't believe it would be very far from these prices. I think the European prices are about the same. The UK and Germany would probably be the most competitive places to shop.

These are all "no contract" prices: you just hand over the cash and walk out of the store with, er, a phone that doesn't work. You can then get contract service from your local favourite airtime vendor. In fact they will probably welcome you in, because you already have a phone and most airtime contracts spend the first 12 months paying off the subsidy that allows them to offer phones for USD 49.