You've got the right idea DGold and you could do that (see Multiple Loops in the Codex for more info). But that's essentially what this plugin is doing - running mini loops with specific criteria.
To get the result you want with the plugin just do this:
<ul>
Category One
<?php c2c_get_recent_posts(2, "<li>%post_date%: %post_URL%</li>", "0000"); ?>
</ul>
<ul>
Category Two
<?php c2c_get_recent_posts(2, "<li>%post_date%: %post_URL%</li>", "0000"); ?>
</ul>
You'll need to replace "0000" with your category ID (check manage->category to find that). You can also change how the listings display. See the plugin homepage for more info on that.