Honestly, I think that the BBS of Sajj is strong. It allows her to remove minions from the board in exchange of her health and Falcius + BBS is 8 damage without taking damage back, which is very powerful.
To me, the main problem of Sajj is that there is no good way to regain the health she traded when removing a minion. Healing spells or damage reduction effects for Vetruvians would help in this respect.
Other than that, the two suggestions in the original post are very good. More synergy with the BBS and more low-cost artifacts would definitely help developing a control build, which is where you really want to use Sajj. Zephir is an awesome card for Sajj, but he dies to easily: giving him 4 health would help, as suggested in another post.
