wp_nav_menu()が出力するliタグ内に独自css名を入れたい

classを追加するだけなら、nav_menu_css_classフィルタを使えばよいのですが、過去30日のようなタイムスパンを指定してカテゴリを得るクエリを発行できるAPIがないかもしれません。

そこを自作すると、下のような感じでしょうか。

add_filter('nav_menu_css_class', 'special_nav_class', 10, 2);
function special_nav_class($classes, $item) {
  global $wpdb;
  $result = $wpdb->get_col("
    SELECT DISTINCT
      t.name
    FROM
      $wpdb->terms AS t,
      $wpdb->term_taxonomy AS tt,
      $wpdb->term_relationships AS tr
    WHERE
         t.term_id=tt.term_id
       AND
         tt.taxonomy='category'
       AND
         tr.term_taxonomy_id=tt.term_taxonomy_id
       AND
         tr.object_id IN ( SELECT ID FROM $wpdb->posts AS p WHERE p.post_status='publish' AND DATE_SUB(NOW(), INTERVAL 30 DAY) <= p.post_modified )
  ");
  if (empty($result)) return $classes;
  foreach ($result as $cat_name) {
    if ($item->title == $cat_name) {
      $classes[] = "new-post";
    }
  }
  return $classes;
}

全てのページでこれが動作するのは、ちょっといまいちですね。wp_get_recent_posts()を適当な数だけ取ってきて、日付を比較するというのも考えられますが、データベースにアクセスしちゃうのは同じなので、変わらないと思います。どちらも、お勧めはいたしません。

なお、$item->titleの判定は書き換えないと動作しないかもしれません。