The problem is that the characters used to represent newlines in a buffer are not the same as those needed to match a newline in a regular expression. As eyal kami suggests, you can fix this by manually replacing the Ctrl-M ^M characters in your substitution with \n, or, perhaps cleaner, you could write a function to do both steps 2 and 3 for you:
You can use vim-visual-multi. Use multi line mode with \\M. Select all occurrences with \\A and do c to change.
Other people will tell you the vim way.
You can also use %s/pattern\n nextline/something/ (or ^v<enter> instead of \n - would surely work ).