Using the same template on all (or many) of your sites, and interlinking them may raise a red flag to Google that you are a linkfarm, which they frown on.
Also, using the same template may create a 'footprint' of what your sites look like, that google can use to connect them to each other, even if you're not interlinking them.
When deploying lots of sites, I take great efforts to minimize the footprint of my sites, even though I don't interlink any of them. But then I'm pretty paranoid when it comes to google.... If they penalize one of my sites, I want to have as few as possible characteristics of my sites that they can use to link my penalized site to my others that haven't been penalized....
For example:
I may use the same template on several sites, but I'll vary the color scheme, layout and widgets that I use on each. Some will be black and red, two-column, lefthand sidebar, with links and related post widgets only. Other sites will be blue and white, three column, righthand sidebar, and many different widgets... I also use different analytics codes on each site, and other pretty extreme measures to make sure that you can't connect one of my sites to the rest via the way the sites are setup...
But, I just re-read your post and said that you'll be varying the background and the logo - so that should help.
You may want to revisit your interlinking plans (I'm not sure what your strategy here is), because using a custom-coded template and interlinking your sites is quite likely to get you some unwanted attention from google.
GS
