Premetto che non conosco PDO. Quindi potrebbe esserci un metodo equivalente a mysql_num_rows().
codice:
<ul>
        <li id="categories">
            <h2>Galleria</h2>
            <ul>
<?php 
                
                $ok = false;
                    $stmt = $db->prepare('SELECT * FROM photo_categories ORDER BY byorder DESC'); 
                    $stmt->execute(); 
                    
                    while(($row = $stmt->fetch()) !== false) {
                      $ok = true;
                    ?>
                    <li><a href="photo_categories.php?id=<?php echo "".$row["id"].""; ?>"><?php echo "".$row["title"].""; ?></a></li>
                    <?php
                    }
                
                 if (!$ok) {
                    
                    echo '404';
                
                }
                ?>
                        </ul>
        </li>
        </ul>