[EricH]

I've run a Mendel, ReplicatorG with Skeinforge, PLA as material... but software doesn't look like it's all of the issue here.

If I got a part like that, the first thing I'd do is check Skeinforge's "this is what I should be doing" window (Skeinlayer and Skeiniso--if Slic3r has any sort of analyze section, open that up and see if you can find a layer viewer) and verify that that bottom is in fact showing up right. If I couldn't do that, I'd assume that it was correct.

Looking at the picture, I'm seeing the following possible issues, any one or all of which could be the issue:
--Not enough width/thickness ratio (on ours, we run very high at 2.6 and don't really have issues with that, but lower and we do). To be point-blank, I'd put that as culprit #2 based on the top view--another couple decimal points up won't hurt you. Look under whatever settings can be found for Fill. (You're showing gaps on top, some not at the edges. The stuff at the edges can be tweaked with another ratio--I think it's overlap with edge.)
--Too much speed for the stickiness. I don't know what surface you're printing on, but whatever it is, if the material can't stick, you may want to run elsewhere on the plate, slow down, or replace the plate covering.
--But the #1 thing I'd say on seeing that: Your head is flying too high above the platform. Have someone grab a feeler gauge and check that you're not much higher than the tip thickness above the platform when the head is all the way down. You'll see a marked improvement if you bring the head down to the platform slightly.