OMG! The above code actually works. Unfortunately, I didn't realize it until it tried a different approach. Here's the alternate code:
<?php
$url = '';
if (!empty($_GET['category'])) {
$url .= $_GET['category'] . '/';
}
if (!empty($_GET['product'])) {
$prod = $_GET['product'];
$prodlist = array("stationery pads", "greeting cards", "magnetic pads", "journals with locks", "spiral notebooks", "sets", "featured");
$actprod = array("01 stationery pads", "02 greeting cards", "03 magnetic pads", "04 journals with locks", "05 spiral journals", "90 sets", "99 new - featured");
$actproddir = str_replace($prodlist, $actprod, $prod);
$url .= $actproddir . '/';
}
if (!empty($_GET['page'])) {
$url .= $_GET['page'] . '.php';
}
echo $url;
?>
My mistake was that the variable I was trying to pass through wasn't plural.

I've learned something from this mistake and I hope others can too. Always double check your spelling.

- Mike