In addition to the increased water changes and gravel vacs, the live plants will certainly help, but be sure to only get low tech, low light plants so that you don't have to jump into upgrading your light fixture or dosing fertilizer and such.
Good plant options would be
Guppy grass (aka najas grass, najas guadalupensis),
Java fern,
Java moss,
Anachris (egeria densa or elodea, sensitive to Flourish Excel and bleach dips; might need a little bit more light than most standard fixtures can provide),
Hornwort,
Most cryptocorynes (crypts),
Most anubias.
Anachris, najas grass, and hornwort are very good at sucking up excess nutrients because they grow so quickly. Anubias are very slow growers, so they might not be quite as good at this but are still beneficial. Anubias and Java ferns should not have their rhizomes buried (the thick almost woody portion where the roots meet the base of the plant) and are best tied to rocks or driftwood (driftwood is usually easier).