The only part of the patch that *should* have carriage returns in it, is the patch to nsvhr.html. So long as no one edits the patch, I can't imagine how other CR's would creep in.
I installed the patches on a Red Hat 7.1 system one week ago following a fresh download of aolserver and the patches, and it patched fine there with no error messages.
If you want to let me login to your system, I can try the patch myself and try to figure out what's up.