make_link.batを見て、確信をもって自己解決しました。
やはり解説が間違っていますね。
mklinkの相対パスは、カレントディレクトリではなくリンクが作成されたディレクトリを基準にするらしいので
mklink /D ..\”Warlords(J)” “Warlords”　はWarlords(J)と同ディレクトリ内のWarlodrsを参照になりますね。
参考：http://pf-j.sakura.ne.jp/program/dos/doscmd/mklink.htm

今どきXPでプレイする人なんてどうせ殆どいないだろうとは思いますが、修正したほうがいいと思います。
蛇足ですが、作業が間違っていない事を確認するためのシンボリックリンク内のフォルダ構造を明記するといいと思います。(Warlords(J)を開くと、AssetsとPublicMapsが見える　とか…)

解決済みでしたらすみません。
自分も同様の現象（Civ4 日本語化パッチ Steam版 1.0.5βにて、Failed　Initializing　Python　というエラーが出る）でしたが、
下記方法で起動はできたので一応報告します。開発の参考になればと思います。
（※時間の問題でとりあえず起動だけ確認しました。完全に動作してるかはわかりませんし、これにて問題が生じても自己責任でお願いします。）

———ここから———
インストールフォルダ(例C:\Program Files (x86)\Steam\steamapps\common\Sid Meier’s Civilization IV Beyond the Sword）直下のWarlordsというフォルダの名前を以下のように変更する。
変更前：Warlords
変更後；Warlords(J)
———ここまで———
以上です。

以下、参考までにこのpythonエラーと思われる情報を記載します。
（_Civ4Logsリンク内のPythonErr2.logの内容をコピペ）
———ここから———
sys.path = [‘..\\WARLORDS(J)\\ASSETS\\PYTHON\\SYSTEM’]

sys.modules = {‘zipimport’: , ‘signal’: , ‘__builtin__’: , ‘sys’: , ‘__main__’: , ‘exceptions’: , ‘CvPythonExtensions’: }

sys.builtin_module_names = (‘CvPythonExtensions’, ‘__builtin__’, ‘__main__’, ‘_bisect’, ‘_codecs’, ‘_codecs_cn’, ‘_codecs_hk’, ‘_codecs_iso2022’, ‘_codecs_jp’, ‘_codecs_kr’, ‘_codecs_tw’, ‘_csv’, ‘_heapq’, ‘_hotshot’, ‘_locale’, ‘_multibytecodec’, ‘_random’, ‘_sre’, ‘_subprocess’, ‘_symtable’, ‘_weakref’, ‘_winreg’, ‘array’, ‘audioop’, ‘binascii’, ‘cPickle’, ‘cStringIO’, ‘cmath’, ‘collections’, ‘datetime’, ‘errno’, ‘exceptions’, ‘gc’, ‘imageop’, ‘imp’, ‘itertools’, ‘marshal’, ‘math’, ‘md5’, ‘mmap’, ‘msvcrt’, ‘nt’, ‘operator’, ‘parser’, ‘regex’, ‘rgbimg’, ‘sha’, ‘signal’, ‘strop’, ‘struct’, ‘sys’, ‘thread’, ‘time’, ‘xxsubtype’, ‘zipimport’)
load_module CvEventInterface
load_module CvUtil
load_module traceback
traceback import failed
Traceback (most recent call last):
File “”, line 1, in ?
File “”, line 52, in load_module
File “CvEventInterface”, line 12, in ?
File “”, line 52, in load_module
File “CvUtil”, line 5, in ?
ImportError: No module named traceback
load_module CvAppInterface
load_module os
os import failed
Traceback (most recent call last):
File “”, line 1, in ?
File “”, line 52, in load_module
File “CvAppInterface”, line 14, in ?
ImportError: No module named os
———ここまで———
(J)を読み込もうとしてるけど(J)が無いということかと思いました。
環境はwindows8.1(64bit)です。

それでは。