Another method to update the solution is using the Sherman-Morrison formula:
http://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula
in your case, $u$ and $v$ are canonical basis vectors, so you only have to solve two systems.

Not sure that this is really your best shot though --- it depends on how many "modified systems" you have to solve with the same starting matrix $A$.