How much should prototype art / graphic design cost?

I have found that graphic artists are not cheap, most people use free art assets and create working prototypes.

I am not a professional graphic artist ( merely a freelancer) and depending on how detailed your project was I would charge around $100-$500.

That's correct--don't invest any extra money for illustrators or graphic designers unless you are self-publishing (something I would also warn against for your first game). Clip art and desktop publishing can already produce nice-looking prototypes. Spend the time yourself to make it attractive enough that people would want to playtest it. Make components that help explain the rules (include helpful symbols on the cards, rules summary on the board, etc.) and also show their connection with the theme. See my blog for examples of many game prototypes that have been published by Berlin designers: http://berlingamedesign.blogspot.com/

Also be wary of agents (and certainly don't pay anyone up-front to sell your game for you). Find which publishers would be attracted to your game, and contact them yourself. Try to make appointments with publishers at game conventions, or approach them there personally if an appointment is not possible. This is how most game designers get their games published (unless they already work for a large publisher's in-house design team). People do business with people.

Word from the pros I've contacted is not to spend a lot on a prototype because, as others have said, a publisher probably will want to tweak the artwork anyway. It is better to do a neat, playable board that gets your idea over and not get caught up in the graphics presentation.
If you are at all handy on the computer and have any decent graphics programs (I use Photoshop Elements and Picture It!7 to do tons of stuff) you probably can do the graphics yourself. And it only costs $35 to copyright whatever you are developing in the way of text and images until you are ready to go for a provisional patent.

Advice from every pro game designer I've ever talked to: don't waste your time and money on copyrights and patents. Once you publish, your game is copyrighted. Patents don't protect game ideas, and are usually laughable (I've heard people filing patents for roll-and-move mechanisms). Game mechanics and themes are not protected by any of this stuff.

And it really doesn't matter. Dominion has a great mechanism, and it's making a lot of money for the designer. It's not completely original though, but that doesn't matter. And it doesn't matter that there are lots of newer games borrowing the mechanism now. Good games do well, and if you are the first to innovate, you'll do better...until someone takes the mechanism you've invented further (that's why people like Knizia do variations on their own mechanisms--before someone else does!).