I see largely the reverse, though certainly it depends on the situation. In my experience, if you were wrong, you just wasted a potentially nontrivial amount of time on developing and supporting infrastructure you will never need.
What infrastructure? Passing a variable along isn't infrastructure and if it takes a non-trivial amount of time then you're either doing it wrong or working on some throw away code. Seriously; it takes no effort at all to do it right in the first place.
I had a specific example in mind, and I guess there are two facets to the issue. One is working with existing code, and to be fair I should probably always clarify when I'm referring to modifying an existing code base. Certainly when building from scratch it's a lesser issue - even so, logging is a prime example. For the same reasons you assert removing a singleton is painful - when I need to add some logging, I may not be able to add it in trivially because there is no log handle readily available. I might not even be sold on the idea the logging needs to stay permanently in code, perhaps I just want to do a quick test? If there's two modules between where I am, and where I need to get the logger from, I might instead opt for a less optimal solution, maybe using conditional breakpoints. Some will question 'why do you need to log there'. Seriously? I'm constrained in what I can log, and where? Logging is a design issue? Perhaps on some projects, but not the ones I've worked on.
To give an example when working with existing code, the example was provided in another thread. I have a code base with hundreds if not thousands of load methods that already exist, taking an XML node in load calls. I want to add in template support, to eliminate duplication within the XML source. This is a somewhat trivial change using a global to store the template database, nontrivial (in terms of time to implement) if I need to pass in a template database to every single load call, along with everything that calls load. Now a template database using GUIDs can be considered global in every practical sense, and I'm finding it tremendously difficult to justify spending days instead of hours to inject the database lookup I need. This is a real world scenario, and a very real potential outcome is this support will never be added, if the cost benefit analysis doesn't add.
The rework is always more signficant. Not only do you have to find where the singleton is referenced, you need to track down everything that references those bits of code and so on. For example, Image::Render uses some logging singleton. To pass the logger into that method, you don't just need to make it available to the class, but the module that owns the class. If you had the references there to begin with, you would've perhaps realized sooner that things were touching bits they shouldn't or designed things more cleanly. The very existence of a singleton promotes worse design.
No matter what the issue, you should know I always get suspicious when someone talks in absolutes, 'always', 'never'. There most certainly exist trivial cases where the rework is not more significant, and I suspect this may well be true in more complex frameworks.
Not only do you have to find where the singleton is referenced, you need to track down everything that references those bits of code and so on.
Nothing you, or someone, wouldn't have had to do in the first place. Refer back to my comment on logging.
You realise that pretty much every unit testing framework in existence runs tests in parallel right?
This is an artificial block, turn off threading for unit tests that do not support threading and make it sequential. Though I'm glad you raised this point, as it could be what many people have in mind when they talk about the difficulties of unit testing code that uses global shared data.
I can't help but feel people are missing the point I'm trying to make though. I'm not advocating people use global shared data. Conversely I've seen projects run quite happily using global shared data. For every project that had serious complications through use of singletons, there are 'n' projects for which it was a non issue, I really depends on how liberally they were used. Where your project sits in the spectrum, I don't know, and I'm certainly not going to just assume (even demand) that you do things one way, and make the claim that you will regret it later if you don't.