I have been able to get the subtitles successfully now on a .avi format. I am still trying for .mp4.
I made a custom profile for my Zune 80gb that exhibits the same problem. I’m posting it below in case someone can spot why using this profile results in no subtitles: 
<profile name=“Zune 80GB” version=“200” device=“zune” tag=“dvdfab” description=“Zune 80GB”>
<common>
<file format=“mp4” />
<audio codec=“aac” channel=“2” >
<freq value=“48000” list=“48000”/>
<bitrate value=“256000” list=“64000,96000,128000,16000,192000,256000”/>
<volume percent=“150” />
</audio>
<video>
<size list=“320x180,320x240,480x270,480x360,640x360,640x480,720x480” out_size=“720x480” />
<outfps mode=“3” value=“0” list=""/>
<encode codec=“h264” bitrate_kbps=“2400” maxbitrate_kbps=“2500” >
<mode value=“real_time” list=“real_time, high_quality” />
</encode>
</video>
</common>
<acodec name=“faac”/>
<vcodec name=“h264”/>
</profile>