First, check the settings on your Maximum Values for what you are limiting your New Products to ...
Next, using your templates and overrides, you should change the:
/includes/modules/sideboxes/your_template_dir/whats_new.php
and change the code to include the line in RED:
Code:
$random_whats_new_sidebox_product_query = "select p.products_id, p.products_image, p.products_tax_class_id, p.products_price, pd.products_name,
p.master_categories_id
from (" . TABLE_PRODUCTS . " p
left join " . TABLE_PRODUCTS_DESCRIPTION . " pd on p.products_id = pd.products_id )
where p.products_id = pd.products_id
and p.master_categories_id = 121
and pd.language_id = '" . (int)$_SESSION['languages_id'] . "'
and p.products_status = 1 " . $display_limit;
Next, check that your products that are showing are using in the table:
products
the master_categories_id of: 121