Making the changes in notepad.exe will definitely not work. When you press "Enter" in notepad, or in many other windows tools, it will insert two characters, a Carriage Return <CR>, as well as a Line Feed <LF>.
If you're unfamiliar with this, think about a real-life typewriter. A <CR> simply returns the carriage to the beginning of the line (the one you've presumably already typed on), and a <LF> will simply move down a line (you'll still be in the same column). When in a Windows program like notepad, the return key will actually insert both of these characters automatically, one to bring you to the next line, and one to bring you to the beginning of that line.
In *nix based systems, the standard is to use a single character to denote a newline. I believe it is a <CR>, but I'm sure someone will correct me if I'm wrong. This means if you try to open a Windows-based text file on a *nix-based system, it will see extra characters it is not expecting (In this case the <LF>).
I'm sure there's a setting in Notepad++ to preserve the line endings on the original file, what this will do is look at the file and look at the very first line ending. If it is a <CR><LF> then it will say "ok, any time the user presses return, I'll insert both". If it sees only a single <CR> then it will know that when you press return, it will insert just a single <CR>.
If you want to be absolutely sure the line endings are not your culprit, you should open the file in NP++. Make the edit you want, and then on the menu, select Edit->EOL Conversion->UNIX Format. If this option is greyed out, then it means the file is already UNIX line endings, and you have some other problem.
As a side note, has anyone found a suitable font for the Kindle with all of it's hinting/rendering uniqueness? I don't mind the default condensed font terribly, but find it less readable than opening up a p-book. I'm not a typographer, so I don't know the traditional paperback book font. Garamond perhaps?