I wasn't able to get primary links to print their children when using theme('links', $primary_links) in page.tpl.php regardless of configuration settings.
Instead, after hours of searching, I found this page on drupal.org which mentions that primary links will output differently depending on whether they're being used as links in a theme or as a block:
http://drupal.org/node/187932
It's a discussion about how primary links' 'expanded' option may appear as 'not working' when they are being used as a theme option instead of as a block. When used as a block, primary links will show the full hierarchy of the list you set up, including children. When used in the theme, unless you overwrite the default settings for how primary links display for your theme, it will only list the top-level primary links. This is what Mark mentioned as the default behavior above, and what I was experiencing.
To solve my issue, I simply took the code to print the menus out of the page template entirely, and then assigned primary links to the region in my template where the code was before.
so instead of:
<div id="nav">
<?php if ($primary_links): ?>
<div id="primary">
<?php print theme('links', $primary_links); ?>
</div>
<?php endif; ?>
<?php if ($secondary_links): ?>
<div id="secondary">
<?php print theme('links', $secondary_links); ?>
</div>
<?php endif; ?>
</div>
I now have:
<div id="nav">
<?php if ($navigation): ?>
<?php print $navigation ?>
<?php endif ?>
</div>
AND specified a region in my .info file for 'navigation',
AND went to the block settings and assigned 'primary links' to my new navigation region.
To get rid of extraneous code outputting into my new navigation region, I also created a new block template for this region that just outputs the content of the block without any additional wrapping divs or heading tags. I ended up with a navigation unordered list that is pretty tidy, and I hope anyone else who is new to drupal and struggles with this issue finds my personal work-around helpful.