Using replace-regexp doesn't remove newlines?

[ozark]

Some of the lines in the buffer have only the single character '#' in
them. I want to remove all such lines.
I tried doing the following:

M-x replace-regexp ^#$<RET><RET>
This replaces the lines with # in them by blank lines. As this is not I
want, I undid that, and instead tried

M-x replace-regexp ^#$C-qC-j<RET><RET>
This just says "Replaced 0 occurrences" and does nothing. Why is this
so? (I also tried C-m instead of C-j, it doesn't work either. I'm using
Linux)

I was able to achieve what I wanted by first replacing the # lines by
blank lines (the former of the two above), and then removing all blank
lines with
M-x replace-regexp C-qC-jC-qC-j<RET>C-qC-j<RET>
but in general, I may not want to remove all blank lines in the buffer.

So my question is:
a)Why doesn't M-x replace-regexp ^#$C-qC-j<RET><RET> work?
b)What is the regexp I must use to do what I intended?

Thanks,