I think some sort of a starter pack is a great idea! I don't think this game needs to be defined as "if you like grinding you'll like this, otherwise find another game". I finally have reached a point where I have enough electrum/cards to try whatever sort of deck I'd like, and that adds a lot to the enjoyability of the game, but it took a long and rather boring grind to get there, and I imagine we lose quite a few players who otherwise would have been great contributions to this community, simply because they aren't part of that minority that enjoys grinding.
Starter packs should of course only be purchasable once (whether they cost real money or electrum). This way you don't have to balance them vs grinding, it just allows a newer player to have more options more quickly, so that they can actually experience the real fun of this game. I like the idea of upping the cost of each subsequent starter pack, so that there's still an accomplishment to having all un-upped cards. I also would agree that the SP's should not include all cards, just enough that it's possible to start say, a basic shadow deck, without either restarting your account or excessive grinding (a little grinding's fine).
And Veterans will still have their upped cards, their rare cards, their nymphs, their forum status, their much higher score, and their experience/skill. As long as the SP idea is well thought out in it's details, I don't think the Vets would in any way need to feel that their hard work was for nothing. I imagine they are all mature enough to be glad the game will be more enjoyable for the newbs.