Hi
Computer science is rather removed from the field I lecture in so I can only give you general tips based on my experience of working in UK and German universities. But in case it helps:
1) Normally, a BSc would have been recognised as equivalent to or slightly higher than a Vordiplom/Zwischenprufung (depending on the university). The major snag in doing a masters in Germany for people having done a single honours UK degree has often been that their Diplom are based on two subjects. So you might have to do some pre-'Vordiplom/Zwischenprufung' work in another subject as well as the Hauptstudium work. In my subject it takes on average 3 years for a German student to complete Hauptstudium but it has to be said this is doing a lot less work that a British undergrad is used to doing per semester so it is possible to do it in 2 years. Check the small print of exam regulations carefully - more traditional German universities often have nasty reuirements lurking there like so much maths, extra foreign languages etc. You also have to pass a German language proficiency exam before matriculating - the Goethe Institut website has info on the standard needed.
2) The way round learning another subject from scratch and a very long Masters degree used to be the 1-2 year specialised Masters (there's a list somewhere on the DAAD site
www.daad.de along with much other useful advice) sometimes taught in English but often with relatively high fees and I have been told anecdotally some recognition problems within Germany.
3) The possibly good news: German universities are very slowly changing to a Bachelors-Masters model, which would make what you want to do MUCH easier. Some universities have been keen about this and have moved ahead rapidly and modernised their degrees at the same time others haven't. The ones that have been quite progressive on this tend to be in Nord-Rhein Westfalen because their state government is insisting this is in place by 2006-7 (Essen and Bochum are probably the furthest ahead). Greifswald in the north-East is another good example.
4) There are massive differences between study in Britain and Germany - you will not have much contact at all with academic staff, no personal tutors, very large seminar groups etc. The facilities vary from place to place but be aware that underfunding in German universities is causing major problems everywhere (avoid Berlin like the plague on this factor). It is however largely free of charge and if you're careful in your choice of university you can have a good experience. I would go for the smaller universities rather than the big city ones and check the ranking in the likes of Stern, Wirtschaftswoche etc to find out where is rated by students, employers and academics.
Hope it helps a bit