Given that theme_breadcrumb returns markup means that for a sub-theme to alter the markup it has to completely rewrite (or copy/paste/alter) the zen_breadcrumb function. I think we can make this a little easier for sub-themes. I'm doing this on a current project and wanted to see if Zen would be interested in this. I could probably create a patch eventually.
The idea is this...
1) Create a zen template.php helper function that returns a render array of the breadcrumbs.
2) zen_breadcrumbs simply renders that render array.
3) a sub-theme can call the helper function to get the render array and then make any alterations.
4) page.tpl.php does not have to change.
I think this would allow for backwards compatibility and give sub-themes the ability to make easier alterations to how the breadcrumbs are rendered.