Crypto currencies are not illegal in Germany. Of course, you would have to make sure to pay taxes if you earn crypto-money as a business, and that is a very complicated territory since the whole concept is new to authorities.

It seems that some banks just try very hard to keep people from using crypto currencies as it challenges the fiat business model.

However, I made some very good experiences with a German bank called Fidor Bank. They even partnered up with bitcoin.de to allow express trading. I don't know if you have to be a German resident to get an account, but perhaps you'll just give it a try.