Well thank you everyone for the suggestions, this forum is really the most helpful one I have been on for anything. This is a great community.
6000 fpm is really fast. According to my math, my bandsaw should be running at about 2000-2500. It does have all of the guides, but like I said, it wouldn't cut the titanium unless I pushed very hard, and at that point I think it was mostly melting, not cutting.
I think what I'm going to wind up doing is getting some bimetal hacksaw blades and doing it by hand.
I actually found a decently priced milling machine on craigslist, and I've been wanting one for a bunch of different things I want to do. Anyone see any reason why that wouldn't work? I feel like it might be more worth it to get the milling machine than a new bandsaw if I could use it for so many more things.