I've used singletons in several large production projects, and never run into a single problem with them. Like any other code construct, it has to be properly designed, and properly used. There are bad ways to use singletons. There are also good ways.
The singleton class I use only has a static pointer to the singleton instance. That pointer is allocated, assigned, and deleted in very precise fashion, on very precise lines of code. There is no problem with the order of creation and destruction as has been discussed here. This is a common singleton arrangement.
About the the criticism of global data. In practice, this is an inconsequential critique. Singletons should only be used for objects which exist for the lifetime of a game, from initialization to shutdown. Whether that object lives in the stack, or is global has almost no practical consequence.
Yes, a singleton can be accessed from anywhere, given you include the header and access functionality via the provided API. This is exactly the convenience that Singletons provide. If you used a non-singleton, this does not change where or when you will need to use that class' functionality. Essentially, you end up doing the exact same thing, except the code to access that class might look a little different, and is often more cumbersome, and may require more layers of indirection.
I agree that, as much as possible, you should attempt to reduce coupling between systems. But again, in practice, the systems in all but the simplest games will be interrelated to a large degree. It is practically impossible to write code where your low level systems (graphics, sound, physics, etc) and higher-level gamesystems are not tightly coupled. Most attempts to do so result in overly-complicated event-driven systems which don't change the interrelation, but just complicate it to the point that debugging and engineering is far more difficult.
Most practical applications of threading I've seen in games involve easily split, repetitive tasks (e.g. processing updates on particle systems, or processing pathing data). Using singletons does not make this any easier or any harder.
Singletons are fine. Just use a proper singleton class, and understand how and when to use them.