The correct call for posting to a user's facebook wall with Python and pyfacebook, after you've established both user authentication via FacebookConnect and gotten stream_publish permission, is:

request.facebook.stream.publish(
    message = render_to_string(template_path, fb_context),
    action_links = simplejson.dumps(
        [{'text': "Check Us Out!", 'href': "http://someurl.com"}]),
    target_id = 'nf')

See that 'nf' down there in target_id? It's not on any of the Facebook documentation pages, but that is the correct string to post to your user's facebook Newsfeed. (For that matter, the fact that you have to run the action_links through simplejson, and that they have to match the PublishUserAction API action_links spec, is also not documented; the documentation says it just needs an array of arrays.) I have no idea how to post to some other user's newfeed, but at least I'm one step closer.

Oh, another important tip: in order to make my news "stories" consistent, I'm using a template to post them to Facebook. The template must not have newlines within, or they will show up on Facebook and it'll look all ugly. Every paragraph should be one long line of text without line breaks.