We lack information, most notably I do hope that we are talking C++0x otherwise it's going to be quite difficult.
The first solution is to explicitly manage your singletons. Most of the designs you encounter on the web focus on simplicity and ease of use at the cost of correctness in the general situation.
The most simple way not to have any issue with your singletons depending from each other is to instantiate them and release them while you are still single-threaded (to avoid synchronization issues) and in the right order.
This is naturally followed by the idea of a Singleton Manager
which is some sort of "super singleton" and will instantiate your singletons and release them accordingly. All accesses to a singleton are done through it so that it can ensure that they are live when accessed. Once again, creation and destruction occurring in single-threaded situation.
It gets much more difficult when we're talking about lazy initialization (on demand). The most simple scheme for that is the local static variable:
MySingleton& Get() { static MySingleton M; return M; }
C++0x finally guarantees that only one instance of MySingleton
will be instantiated which makes things much easier! However you do have here the "dead reference" problem.
In C++ the destruction order of static objects is simply the reverse of the construction order, therefore one solution is to mandate that any singleton used within the destructor of a singleton object be used in the constructors (ALL of them). This way you actually guarantee that it will be built before, and thus destroyed after.
Note that lazy instantiation is difficult in a multithreaded environment in C++03 (or sooner) because there was no guarantee that a single instance would be created... and it's extremely difficult to grab a lock at that point (after all, the mutex is itself a singleton... isn't it ? ).