Drupal 6.19 - cannot add node links to primary-links
Issue solved.

Looks like that with the large menu tree, Mysql packet size was exceeded.

I just added the following to mysql config (my.ini) and the issue resolved:

[mysqld]
max_allowed_packet = 16M