Having started re-watching Voyager the whole way through I've had time to think carefully about this one. There's a lot of Harry hate out there (no, Harry Hate is not his stage name when he performs clarinet arias in Sandrine's), but I think I need to go on a wee small rant (being as I'm in the mood for one), and I'm interested to see who agrees with me.
First up, in seasons 1 & 2 there have been a butt load of episodes where, far from doing nothing, Harry Kim does everything. Saves the ship, keeps the coffee from going cold, creeps to the Captain and generally has the whole plot revolve around him. He keeps doing it further into the series as well, in fact much of the problem solving comes from the Janeway/Torres/Kim power combo (and later just Seven of Nine on occasion as well), unless it requires shooting things in which case Paris and Tuvok handle it, or singing, in which case we all know Il Doctore has it more than covered.
So here's the big question.
In seasons 4 through 7, what the bloody hell does Neelix do? Gets on my tits is what. Having sympathized with Tuvok a great deal when he attempted to choke a holographic version of him to death in the Holodeck (that was pure television catharsis) I just don't honestly see what use he was to the crew other than doing a bit of cooking here and there, representing the portion of the crew that appeals to the tranche of fans that would be the sort to like Jar Jar Binks, and providing the comic relief every now and again.
I suppose you could say that his aiding Seven to become more human might hit the list. Fair dos. However, surely that's what Janeway was for. And I think Chakotay definitely had a good go at helping her "become more human" if you'll excuse the slightly obvious joke.
One thing's for sure - he wasn't there to guide the sodding ship. How do I know that? Well, because I personally doubt that any one person can know the entirety of a quadrant inside and out due to the large amount of time it would take to travel from one end of it to the other. After Kes moved the Voyager 10,000 LY to deus ex them out of Borg space (so that they'd still be able to have new Borgy stuff in S7) Neelix's usefulness was logically over. So bye bye baby. Find another Deus Ex to get 'em out of hot water/nanoprobes and kosh the gimp.
Moving to a more logical perspective, it seems that the entirety of the decision of the cast change was based around sex appeal. I have my emergency kit ready, so shoot me down in flames on that one if you want to, but the whole "appealing to 25ish year old males" was the idea of the change from what I can fathom. Therefore, replacing an attractive female actress with another attractive female actress with bigger breasts seems to have been a little bit of a dodgy decision, unless it was based purely on testosterone on the part of the execs. Bear in mind this followed a decision to keep Garrett Wang because of his appearance in the top 50 most beautiful people, and you can see that that made them think "Ah, let's bear in mind the 25ish year old women too".
If they REALLY wanted to make the call like that then to be honest keeping Kes and Harry would have been a great idea. Firstly because there would have been two ladies for the guys to drool over and one guy for the ladies to drool over, following the casting director's logic. Secondly because I'm 100% sure that Kes would have added another dimension to any confrontations with the Borg. Have they encountered the Ocampa before, and how are they going to counter their telekinesis.
Not how are they going to stomach the Leola root stew...