Normally it should work. Some people played the map already^^.
here you have a filelist of the new files. Check if all files are in the correct folter. Otherwise i dont know why it doesnt work.
esf/maps/afc_budokai.bsp
esf/maps/afc_budokai.txt
esf/afc_budokai.wad
esf/gfx/env/afcbudokaibk.tga
esf/gfx/env/afcbudokaidn.tga
esf/gfx/env/afcbudokaift.tga
esf/gfx/env/afcbudokailf.tga
esf/gfx/env/afcbudokairt.tga
esf/gfx/env/afcbudokaiup.tga
esf/sounds/ambience/afc_gong.wav
esf/sounds/ambience/afc_wind.wav
esf/sprites/ballsmoke.spr
Or download it again and install it for a second time.
budokai
hope you are able to play it.