In Canada cell phones certainly work at all altitudes as it's the same system I am sure this is the case anywhere.
As others have said it's the phone companies themselves that have the greatest problem with airborne use. As far as interference with a/c systems I think the verdict is still out. There is a system available in the USA aimed at the corporate aircraft world called Aircell. It ties into the existing cell network while on the ground but the difference is that airborne it only hits a limited number of cells so as to not flood the system. I presume it's the same frequency spectrum so I am not sure where that leaves the whole interference thing?