First of all, what I think you are in need of, is some kind of reference to base you pixels on, since it doesnt really look like a sword.
IMO what is going wrong here aint nor AA nor dithering, but just a matter of composition and wrong palette usage
Here is one, fastly googled:
http://www.northlandgifts.com/images/items/VA54100A.jpg Now stare at the ref., and squint your eyes to simplify the shadows, and pixel and shade the sword as what you see.
Dont pixel from the top of your head if you arent really sure of what you are doing.
Use a reference to base on and as said before, pixel what you see, and not what you think it might look like.
And same with the palette, pick it according to what you see, similar tones to what you see.
Not trying to sound harsh, but you might want to consider repixelling the whole thing rather than just editing.
Just my 2 cents, and hoping to see more updates.
Good luck