BlackAce, from what I understand it's very very rare in Germany for elections to be held before the end of the government's term in office. What happened was that Gerhard Schröder, the Bundeskanzler, was very unpopular in public opinion polls.
He arranged for a vote of confidence from the Bundestag (parliament) in order to see if he still carried the support of the elected representatives. Knowing that the members of the parliament would probably vote in his favour just to avoid an election, he knew that the people of Germany wouldn't be content with the outcome.
Schröder had to arrange for his own government to be defeated in the confidence vote in order to force the President to dissolve the Bundestag and call for elections.
Under the Basic Law, Köhler wasn't required to do so, though it was within his powers. He finally decided to put it to a vote in order to clarify whether Schröder has a mandate to run the government.
Under the Westminster system of parliaments (Canada, UK, etc), this stuff happens all the time when no single party has a majority, but it's rare in more stable German-style systems.