Definitely. I often find myself doing a bit of a double-take when the topic suddenly shifts, and then I find the little greyed-out "[Deleted]".
I'm pretty sure that's the case. It's not as bad when the deleted comment is at the top level, but it's anywhere farther down in the thread, it's difficult to figure out where in the hierarchy it is, in my experience. Perhaps keeping (but blanking the info in) the comment post header would better delineate the deleted comments without disrupting the visual thread?
I assume that many times, the problem instead is that replies to deleted comments are downvoted because the comments lack the context to appropriately judge the content. Other than people quoting from the comment they're replying to, I'm not sure what is a good way to deal with this.
This thread contains an example: https://news.ycombinator.com/item?id=9458661
Edit: off-topic UI question—my comment was a reply to a comment that its author subsequently deleted. Is that unclear to the reader?
I've noticed that replies to comments marked [flagged] or [deleted] seem to get downvoted more, and am wondering if that's because it isn't obvious that there was a parent comment and it's no longer there.
Edit 2: Thanks for all the replies. It's clearly a problem and I've put it on our list to fix.