It is true, sometimes singletons can create problems, that you won't have without them.
I try to give you a list of my thoughts on this matter:
The most severe would be, that your software has circular dependencies. If you are working on a SOA architecture it can happen quite fast, if you are not careful.
Also singletons can often lead to very close coupling of your classes, which makes you job as a tester really really hard.
If you work on a big project and the way another class can get an instance of your Singleton changes, you will have to change lots of code. This can also happen without singletons, but I have the feeling, that it happens more often with singletons.
But sometimes a singleton is a nice idea and you should stick to it. Even in AS3 you can use singletons with the famous private class argument constructor workaround. As a heuristic when not to use singletons, i would suggest thinking about, if the class needs lots of references to other singletons.
And with some thinking you can also make your singletons testable.