Did they give a reason for not accepting your BSc? What college did you receive your degree from? It is highly unusual, they should at least accept some of the courses you did, so you don't have to start from scratch. A BSc in Informatik covers the basics of computer science, information theory, math and software engineering. There are more specialized degrees depending on which university you plan on going to. The more practical degrees are at "Fachhochschule" (think of community college). With some of those, you might have trouble doing your MSc with a proper university.
Generally studying at a German university is more strict and theoretical than you might be used to from the states. Prepare to learn a lot from books and lecture notes not so much from courses and people. My biggest advice is to get acquainted with the rules and formal requirements of your university. Otherwise it might bite you in the ass.
That might not apply to Universities that don't profit from the "Exzellenzinitiative" (what it sounds like). I got my BSc from one of those and it wasn't too pleasant.