I think the very interconnected and serialized nature of the novelverse makes it somewhat impenetrable to new readers at this point, 15+ years in.  Everyone's changed so much, it's no longer the universe the TV shows got them into.
		
		
	 
I agree with you that the serialized nature of the current continuity could prove daunting to a new reader. However, I think the writers typically do a good job of catching readers up on what's going on. I was able to jump into the Destiny trilogy without feeling lost, for example.
I think the internet has helped change things as well. If a new reader wants to find a good jumping on point, or wants to find some background info on an unfamiliar character, they can do so with a few keystrokes.
I wonder how many first time readers are impulse buyers in a bookstore?  I doubt there are many these days. Even when I make an impulse buy these days I'm able to google first.
The second point you mention about the characters having changed so much is a bigger problem, imo. A new reader probably is seeking out more of what he loved about the series when he buys a novel. There is a good chance they are going to be disappointed. Hell, I've enjoyed most of the current continuity and a part of me still misses the status quo of the series. 
I think the key is that, if you're going to change the characters, it better be damn good. So good that a first time fan thinks "This is 
fantastic - how did we get here?" and goes to buy the previous books.  The early DS9 relaunch pulled this off perfectly.
	
		
	
	
I am really surprised that you liked that one. Parts were fantastic, but there were some scenes where I was totally lost. I assumed that it would be even more confusing to someone who spoke English as a second language.
Speaking of books that you like, are you the person who recommended "The Death of Princes" in an old thread? I was thinking about ordering it, but the Amazon reviews are all over the place, as they often are.