I don't think that profit-share is a non-starter out-of-hand, but you'll need to manage your expectations. Imagine that roles are reversed -- you work as a professional programmer in your day job, and an artist approaches you to work on a project for profit-share. Their idea sounds somewhat interesting, but it isn't quite your cup of tea, and you've got a hundred ideas of your own that would probably be more fulfilling. What do you do?
This is why people already making money on their talents are hard--though not impossible--to secure on a profit-share basis. And you may not be competing only with their day jobs, but also other freelance or moonlighting work that might either be paying up front, or which simply might hold more appeal for them. A talented artist can literally pick any project of their choosing to become involved in.
Less experienced, qualified, or skilled artists are more available, but may not give the level of work you would prefer. If you're not willing to settle, a less-skilled artist might be willing to work for less, and perhaps their skill will grow, or they will at least be able to carry you to a point where you can recruit a more skilled artist to help polish things up. If you were to end up taking this route, you need to be clear and honest up front about what you're offering and what you expect, and you need to stick to it -- everyone needs to be on the same page, or that artist is going to feel used when someone better comes along. Even if their art never makes it to the final product, they should still be compensated in a measure equal to the time they put in and their skill level, and they should get a game credit or whatever other fringe benefits they have coming (The credit and fringe benefits are often what lesser-skilled artists are after, because they're trying to build up their portfolio and experience).
Money does two things for a part-time developer in securing an artist -- firstly, it guarantees the artist some compensation for his work, and secondly it says that you are serious about completing this project. A profit share of an unreleased project is exactly $0, regardless of how many hours of work everyone has put in. You need to trust that the other person is just as committed to you to delivering a product that's complete and suitable for sale. Its hard to trust a stranger, or even someone known to you when you're talking business, but being compensated or holding some kind of collateral can make that less of an issue.
Keep in mind, you don't have to do pure up-front payment or pure profit-share. You still need to offer enough up front to be taken seriously, but there's many more people willing to work for 25-50% up-front than there are for 0%. If you don't know what kind of offer to make, you can make a similar proposal to what they make in many creative industries where a producer or publisher is involved -- You define the pay-rate as a royalty or profit-share, but pay some figure $X up-front to secure the work; when the project is complete and earning money, you begin to tally their share, but you don't pay the first $X because its already been paid up front. They only get the profit-share they've earned above and beyond $X, and if their share of profit never grows beyond that, then $X is all they get.
