Why are there "template_" and "theme_" prefixes instead one?
The functions whose name start with theme_ are theme hooks, while the functions whose name start with template_ are preprocess and process functions implemented by the module that implements the relative theme hook.

For example, theme_image() is a theme hook that renders an image.   template_preprocess_node() is the preprocess function implemented by the Node module, which the module implementing the node theme hook. (See the first code lines of node_theme(), the hook_theme() implementation done by the Node module.) There are other modules that can implement a preprocess function for the node theme hook, but for those modules, that preprocess function is named MYMODULE_preprocess_node(), not template_preprocess_node().

A theme can implement both a theme hook (see bartik_menu_tree()) and a preprocess function (see bartik_preprocess_node()). The difference is that bartik_menu_tree() overrides the default implementation (theme_menu_tree()) when the current theme is the Bartik theme, while bartik_preprocess_node() doesn't override template_preprocess_node(), but it is executed after it. (See the documentation for theme().)  

As for using two prefixes, the reason is to documenting the purpose of the function. Even if theme_ were used in both the cases, the difference between theme_image() and theme_preprocess_node() would still be clear, but it would require you to read what follows theme_. With the current implementation, you just read the first word of the function name.