Hello,
I would hazard a guess that any issues would be in your css file. With menu items, ul and li settings tend to be overridden by menu- specific lists, including li.leaf, li.expanded, etc. I would look there before breaking apart your php template files.
But, the stylesheet doesn't tell drupal to put in <ul> where there should be a list. Does it? Just as a test, I removed the stylesheet, and the problem still existed. Any normal block with links gets wrapped in <ul></ul>, but any menu I've created, the lists within them are not wrapped in <ul></ul>.
Is there anything else it could be?
- jody