Go speak with your department chair. Normally when faculty leave, a chair will do the best they can to accomodate his stuff, and if you have a fellowship you should be quite attractive. Also, go personally and speak with prospective advisors in commuting distance with research that appeals to you. Think about labs where even if you must change projects, things are related enough that they may fit into a job seminar. Again, don't underestimate how attractive you are with your own fellowship.