1) Singletons do make sense when they represent a true physical singleton - for example, you only want one piece of code drawing directly to the screen, the Window Manager, which should indeed be a singleton.
2) Most of your problems stem from the us of GetInstance() not from the use of the Singleton pattern in and of itself. For example, without GetInstance(), the other way to get a reference to the Singleton object is to pass it in to the object that is going to use it. This indicates the dependency in the client class's interface, and also makes mocking out the Singleton for test purposes a real possibility.