The situation with Debian
As a late response to this question, what @jmtd said is exactly what happens periodically in the Debian archive.
Packages are recompiled with newer toolchains (compilers, linkers, etc.) and, when recompilation fails, bugs against the packages that failed to be compiled are filed with the indication of FTBFS ("failed to build from source").
Such bugs are generally an indication of something bad happening and are usually ranked with high severity and given the status of "release critical" bugs, meaning that a new release can't be done with those bugs unsolved.
In particular, Lucas Nussbaum has been recompiling the whole archive of the Debian Project in a grid as a means of some Quality Assessment.
Recently, though, Sylvestre Ledru and some other Debian Developers have mentored students in Google's Summer of Code of 2012 to allow substitution of both GCC by Clang and libstdc++
(GCC's support library for C++) by libc++
(Clang/LLVM's counterpart).
There is a site where the results of compilation of the whole collection of Debian packages were published and further reports were documented by LWN and the program for decoupling the Debian build process from GCC was successfully concluded.
So we may soon see a flavour of Debian compiled with clang/llvm, depending on how much support these successful results can gain.
The newcomer
There is, as of this update (2016-08-16), a new version of a traditional Linux distribution compiled with clang and llvm, OpenMandriva Lx 3.0, now in its final release. According to its notes, it is compiled, as much as possible, not only with clang and llvm, but also with "regular" high optimization levels and also with Link Time Optimization (LTO).
LTO
While the main subject of the question and of this answer is llvm/clang, to be fair, it should be noted GCC also features LTO (more background on LTO).
In theory, LTO, as seen in newer clang/llvm and GCC, has the potential of making not only the resulting binaries faster, but also having smaller memory requirements for the text-section of the programs (and the Linux kernel is one potential benefiter of LTO).
I have not read how much OpenMandriva Lx 3.0 uses LTO across all the programs, but I'm excited that it uses clang/llvm + LTO and I would love to see people doing multiple independent benchmarks comparing and contrasting "regular" GCC-based, non-LTO-optimized distributions to OpenMandriva Lx 3.0.
FreeBSD 10 will use the BSD-licensed Clang compiler instead of GCC for 32- and 64-bit Intel x86 systems. The only thing preventing a wholesale switch on all CPU platforms FreeBSD releases on is developer time and interest.
As for FreeBSD 9 — which was just about to be released when this question was first posed — there was talk about making Clang the default compiler, but there were enough problems with it that they decided to ship Clang alongside GCC, and leave GCC the default for this release.
As for why FreeBSD didn't try moving to a non-GPL compiler years before, or perhaps even create their own, the reason is simple: it's hard.
Any undergrad CS student can write a compiler — it may even be a course requirement — but writing a good compiler is hard. Writing a good compiler is harder still when it needs to be for a language like C or C++. The task becomes still harder when you make the reasonable decision that the new compiler needs to at least approach the performance and capability of GCC, which has a couple of decades worth of development behind it.
Because of that, GCC 4.2 is still the default compiler on FreeBSD 9.
GCC 3.4, 4.4, 4.6, 4.7, and 4.8 are in the FreeBSD 9 Ports tree, by the way, and some version of GCC is likely to remain in Ports for many years to come. There's a lot of software packages out there — many of which are in FreeBSD Ports — which only build with GCC.
Best Answer
Summary: The primary reason for switching from GCC to Clang is the incompatibility of GCC's GPL v3 license with the goals of the FreeBSD project. There are also political issues to do with corporate investment, as well as user base requirements. Finally, there are expected technical advantages to do with standards compliance and ease of debugging. Real world performance improvements in compilation and execution are code-specific and debatable; cases can be made for both compilers.
FreeBSD and the GPL: FreeBSD has an uneasy relationship with the GPL. BSD-license advocates believe that truly free software has no usage restrictions. GPL advocates believe that restrictions are necessary in order to protect software freedom, and specifically that the ability to create non-free software from free software is an unjust form of power rather than a freedom. The FreeBSD project, where possible, tries to avoid the use of the GPL:
FreeBSD and the GPL v3: The GPL v3 explicitly forbids the so-called Tivoisation of code, a loophole in the GPL v2 which enabled hardware restrictions to disallow otherwise legal software modifications by users. Closing this loophole was an unacceptable step for many in the FreeBSD community:
Because of GCC's move to the GPL v3, FreeBSD was forced to remain using GCC 4.2.1 (GPL v2), which was released way back in 2007, and is now significantly outdated. The fact that FreeBSD did not move to use more modern versions of GCC, even with the additional maintenance headaches of running an old compiler and backporting fixes, gives some idea of the strength of the requirement to avoid the GPL v3. The C compiler is a major component of the FreeBSD base, and "one of the (tentative) goals for FreeBSD 10 is a GPL-free base system".
Corporate investment: Like many major open source projects, FreeBSD receives funding and development work from corporations. Although the extent to which FreeBSD is funded or given development by Apple is not easily discoverable, there is considerable overlap because Apple's Darwin OS makes use of substantial BSD-originated kernel code. Additionally, Clang itself was originally an in-house Apple project, before being open-sourced in 2007. Since corporate resources are a key enabler of the FreeBSD project, meeting sponsor needs is probably a significant real-world driver.
Userbase: FreeBSD is an attractive open source option for many companies, because the licensing is simple, unrestrictive and unlikely to lead to lawsuits. With the arrival of GPL v3 and the new anti-Tivoisation provisions, it has been suggested that there is an accelerating, vendor-driven trend towards more permissive licenses. Since FreeBSD's perceived advantage to commercial entities lies in its permissive license, there is increasing pressure from the corporate user base to move away from GCC, and the GPL in general.
Issues with GCC: Apart from the license, using GCC has some perceived issues. GCC is not fully-standards compliant, and has many extensions not found in ISO standard C. At over 3 million lines of code, it is also "one of the most complex and free/open source software projects". This complexity makes distro-level code modification a challenging task.
Technical advantages: Clang does have some technical advantages compared to GCC. Most notable are much more informative error messages and an explicitly designed API for IDEs, refactoring and source code analysis tools. Although the Clang website presents plots indicating much more efficient compilation and memory usage, real world results are quite variable, and broadly in line with GCC performance. In general, Clang-produced binaries run more slowly than the equivalent GCC binaries:
Conclusion: It's highly unlikely that compilation efficiency would be a significant motivator to take the substantial risk of moving a large project like FreeBSD to an entirely new compiler toolchain, particularly when binary performance is lacking. However, the situation was not really tenable. Given a choice between 1) running an out-of-date GCC, 2) Moving to a modern GCC and being forced to use a license incompatible with the goals of the project or 3) moving to a stable BSD-licensed compiler, the decision was probably inevitable. Bear in mind that this only applies to the base system, and support from the distribution; nothing prevents a user from installing and using a modern GCC on their FreeBSD box themselves.