Problem printing Primary Links with children

I am creating a custom Drupal theme for Drupal 6 and have been struggling all day to get the primary links to print with the child objects.

There are hundreds of possible solutions around, but not one of them work. I must be doing something wrong.

Here is what I would like:

    <ul>
      <li>Item 1</li>
        <ul>
          <li>Sub of 1</li>
        </ul>
      <li>Item 2</li>
    </ul>

The problem is no matter what I do I am only getting the top level links. I cannot put the primary links in a block, which most solutions require.

Thank you