That's correct. You need the Meldebescheinigung (given during the Anmeldung) to open a bank account, and you need a bank account to find an apartment, and you need an apartment to do the Anmeldung (it requires a fixed address).
It's pure madness. I actually run a blog documenting the (sometimes insane) German bureaucracy. It's not nearly as bad as people think, but things like getting an Ausländerbehörde (immigration office) appointment can be a real pain.
Fortunately, it has improved a lot in the last 3 years. The Settle in Berlin article is completely outdated.
http://allaboutberlin.com/guides/berlin-auslanderbehorde-sam...