Well, can't figure out what all I did exactly. :

I diff'd my 3.6.9-final tree to see the differences, but there wasn't that much different. I can only assume that all of the trouble I had with it was fixed before I did the final release (but I don't remember, a lot was going on at that point).
Going over the project file diff, then only things that I see are that Theora.frameworks is added to the frameworks list and copy-files set, and I added "./Frameworks/Theora.framework/Headers" to the header search paths, immediately after the Vorbis include of the same thing, for release and debug configurations. Beyond that there are various other project file cleanup stuff, but nothing directly related to Theora.
If that doesn't work then just try that same project file that I used for the final release. No promises that it will work 100%, since I have somewhat abused it over time, but it's something to try:
http://icculus.org/~taylor/fso/misc/project.pbxproj.gz