I thought it might be fun to take a look at the new starter decks and see how I might try to upgrade them, using only cards from the Revised Core set and the four starter decks themselves. Some of these decks could be played together still, while others (primarily Dwarf - Gondor and Gondor - Rohan) do use some of the cards from other starter decks, so you wouldn't be able to build all four of my "upgraded decks" at once. This would primarily be a way for a solo player, or 2p group, to start slowly deckbuilding by making some small changes to the existing decks while trying to keep the overall idea of the deck the same.
The Riders of Rohan deck was the toughest one for me. It is really lacking a defensive option, so it is going to be fairly reliant on chump blockers. That, combined with Lothiriel shuffling cards back into the deck and the occasional ally being discarded for their effect means this deck needs some way to recycle allies. Stand and Fight is the best option to help solve that problem, so it needed to go into the deck. A couple other, non-Rohan, tactics allies from other packs can really help out as well, so Defender of Rammas and Galadhon Archer seem like natural fits, despite their lack of trait synergy. The defender in particular will help by allowing you to not be forced to chump some of the smaller attacking enemies (and can even take a decent sized attack the round it enters play if you trigger Hirgon).
I still think this is probably the least consistent of the four decks, but the addition of a few more cheap allies should make it a bit more usable than the directly out of the box deck.