If you have the original .PSD files, which you should if you paid for someone to do the graphics for you, then it is a snap to adjust the banner. If you don't have the original .PSD then you have a bit more work to do, although it is hardly a task fit for Hercules. Any half way decent graphic artist can fix this right up for you.
Not sure what type of files you have from the banner, if you have the source (.PSD) and some experience with designing then it should be fairly easy to change the banner your self. Now I am not going to throw my designing services to you here, but if you are looking for new banners then I would suggest you take a look over in the BST (Buy, Sale, Trade) area. There are alot of designer there that can help you and give you a good new banner. Also, if you don't want to limit your options you can always go with a contest over in the BST forums as well and pick the best ones you like so you have a variety to choose from. Hope all goes well for you.