Check out the two using identifont.com's comparison tool:
http://www.identifont.com/differences?first=Palatino&second=Palatino+Nova

Despite the line beneath the samples that states there were no differences found, the two versions do differ—as you've discovered. Besides the letter spacing issue, Nova's A has a higher crossbar and its Q a longer tail than the original Palatino, just to name two instances.

Interesting. Is it just me or does it seem as though there is something inherently off with the spacing in Nova? I've attached a one word comparison of the two.

Could it be that the online page does not show the fonts' kerning properly? (Or possibly just in your browser of preference.)

There are (at least :) three competing systems for kerning: TrueType's original kern, which is rather easily to implement and therefore quite well supported, Adobe's Type 1 .afm based kerning (rare; proper Type 1 support seems rapidly dwindling), and finally, OpenType's GPOS tables - hard to implement correctly.

It seems to me that the Nova has slightly more delicate serifs. But Aldus is better for text.

Of these two samples the original (not nova!) is far superior both by weight and fit

Could be a kerning issue. The web pages is not the way to judge this.

The differences in the glyphs themselves are not that significant, but I do see some curvature in the stems. The serifs are a bit thinner (not good).

The "new and improved" Palatino is anything but. It is slightly lighter, the serifs are shorter, and overall the face has a softer feel to it. It is a pale imitation of Palatino.

I have the original from 1950. The newer ones suck.

Nice u got original ?
Is very old

I'm definately not feeling nova as much as the original. I more liked the idea of the font being modernized than the reality. Yes, perhaps I should not judge the kerning based off a web preview. Does anyone suggest a font (not aldus) that would be a better Palatino replacement? Something with a more subtle nuanced modern flair but still classic.

Yep, got it. Got Softmaker file, then fixed it. It's not very good, so I had to do a lot of work on it. It looks very good now.

Trump Medieval?

I notice also that the axis of stress has been made more vertical. More like Aldus. The new font is idiotic!

I'm a little confused. Was Zapf personally involved in this update?

Yes. But he has obviously gone senile. It's worse than the previous version!

I'm guessing that the Nova is a text version of Palatino (essentially a display font) because Joe Shmoe is hooked on the "Palatino" name, and doesn't realize that Aldus is already the text version...

Yeppers....

In my opinion, Palatino Nova and Aldus Nova are hugely disappointing when it comes to kerning — check the “th” pairs below.

Really?! That's nuts.

The difference between Aldus Nova and Palatino Nova is less than it was before. Idiotic! Why reduce the ascenders of Aldus? Zapf was getting senile.

Maybe Zapf had nothing to do with it. His name tho...
Related, the last paragraph here: http://typographica.org/typeface-reviews/palatino-sans/

Second one is better. (even if some kern pairs may lack)
Nicer more organic letter forms, wider (better) spacing. As Palatino standard is too narrow in my eyes.

From top:
Palatino 1950
Palatino
Palatino Nova
Aldus Roman
Aldus Roman Nova

One can see what a disaster the 'Nova' fonts are. The serifs and thin strokes of 'Palatino Nova' are noticeably thinner than the predecessor version, which was already hideous enough. What an abomination!

Note the capital 'E' and 'F' in all five fonts. They have been narrowed in Palatino Nova, and widened in Aldus Roman Nova. What? Also, note how the crossbars in the E and F in the original Palatino 1950 and Aldus Roman are not at the same height (the crossbar of 'F' is lower). This is to achieve a better 'balance' in the 'F'. The crossbar of 'F' in both Novas is even with that of the 'E'. What an abortion! How can these idiots put out such crap? Also, the diagonal stroke of 'Z' and 'z' should be thin (as it is in Palatino 1950 and Trajanus), not thick. The stress is nearly vertical in Palatino Nova, much like that of Aldus Roman. The ascenders of Aldus Nova are shorter than those of Aldus Roman, and the characters of Aldus Nova are all wider.

Overall, the changes make Aldus and Palatino more similar. What idiocy!

Well. I'm glad I wasn’t just seeing things. I think I'm going to steer clear of the Nova fonts. I wish there was more of a write up on what they were thinking.

They weren't. The Nova styles are a horror.

See:

http://en.fontke.com/family/256133/style/

Any more comment on this?

jo: die nova version ist topp -- man muss nur wissen, wie man sie einsetzt.

Nonsense. The Nova fonts are missgeburt!