Edit: Posted this before I saw Bob's post; but anyway.
I'll get the ball rolling with my favourites:
What's so great about it: Shipping worldwide from Japan, "Nikonekobaby" sells "That's" branded Taiyo Yuden printable media, including Watershields. Their stock varies, sometimes wildly, but usually you can find a full range of "That's" media, much of it printable, some of it Watershield, in volumes ranging from 10 pack spindles and jewelcase packs (for DVD-R and -R DL) to 50 packs (DVD-R and CD-R)
The store also has a nice range of Blu Ray discs. Shop is a bit pricey but if you want the best and you're stuck, this is one option:
Name: Genesys DTP
What's so great about it: Two things - first of all, it sells Taiyo Yuden in quantities ranging from 10-600 discs, where for example, you can buy YUDEN000 T02 Silver Printable by the 10 pack, in addition to a full range of Verbatims, BD-R/REs and other good stuff, it also sells some very nice Prodisc printable-top-coloured substrate CD-Rs.
Ships: Worldwide from Connecticut (U.S.A) very reasonably by U.S. postal service.
Specialising in small-quantity media sales, this is the perfect shop for Europeans to try out different types of media - particularly if you've just got a new disk printing inkjet printer and want to try out white printable, silver printable, coloured printable media of most every description, they have Taiyo Yuden discs of all types in quantities as low as 5, and a wide variety of other odds and ends.
Ships: To the U.K. Ireland and possibly continent-wide by Royal Mail.
Name: Card-Rohlinge (Heidelberg, Germany)
Selling blank media and disc replication supplies, they have a section for Colored CDs. They used to have all kinds, red, blue, black, green, even pink, but their manufacturer MPO/HiSpace had to exit that business. Discs were expensive so they were better to focus on value added services anyway.
However, in the coloured disc section, they still have some coloured discs left, i.e. green and black, as well as faux-vinyl.
Ships: to Europe.