Documentation of textlib.replace_links is insufficient. The behaviour depends in on type (which is not really helpful imho).
e.g.:
>>> import pwb, pywikibot as py
>>> from pywikibot.textlib import replace_links as rl
>>> t = '[[Foo#bar|baz]]'
>>> s = py.Site()
>>> rl(t, ('foo', 'Bar'), s)
u'[[Bar#bar|baz]]'
>>> rl(t, ('foo', py.Page(s, 'Bar')), s)
u'[[Bar#bar|baz]]'
>>> rl(t, ('foo', py.Link('Bar', s)), s)
u'[[Bar]]'Please provide some samples how to replace links.