Would it be feasible?
In short: yes, theoretically.
Long answer: It's going to take a while and it will be a lot of trial and error until you know what your doing then you have to figure out how to make the output from the machine learning make sense (I can almost guarantee it's going to butcher whatever language your going to try and teach it, at least for the first few attempts). It might be worth looking into making it detect what kind of tone you said it in, then generate a pre-defined bit of text in response. For example if someone if being a dick you might be harsh or possibly leave out a bit of information to make it harder for the player.
How long would it take?
Depends. what level of interaction do you want?
If you want every possible combination of words to be recognised properly you could be sat there for decades creating the singularity... On the other hand if you only want basic chat functionality you could have it done in a few months.
People have been trying to make proper chat programs for ages (at least 50 years) all of the attempts have taken a long time and produce mediocre results but on the other hand they are trying to make a program that is able to hold conversation to the level of the turing test. If you limited the scope and concentrated on building some way of extracting key words from the sentence then feed that into the machine learning portion you might be able to make something similar to what you want.
Are there any opensource AI which can be downloaded and trained?
There are a few out there but I don't know enough about them to tell you which ones would be good for this application.
Lucida AI, a program to make a virtual assistant think google search only locale on your machine.
Mahout, appears to be a library to enable scale-able machine learning. So you might want to look into this for the actual learning part as it should be able to scale so that you can get it to "learn" faster. small plus is that it's an Apache project so you can use it a for commercial software.
personally i'd take a small course into machine learning to see what your getting into to see if you could possibly stand spending an extended period of time developing. Udacity has a free course on it for deep learning which is a branch of machine learning or if your really dedicated this course specifically for machine learning however it costs a bit of money (200 USD with a 50% discount if you complete the course in a year).
What key issues do you think I overlooked?
In the end if your still going to make a game after going to all the effort of this, is it going to be a game that is "fun" or at least a game which will be an interesting and fun experience for the player that won't know the backstory of you developing an AI from the ground up. Will there be enough content to keep people engaged with it?
How are you going to get the AI to naturally get across narrative to the player without making it sound forced. An exelent example that i heard recently was that some scientists looked at a bunch of data and found a correlation between amount of Ice cream sold and people drowning. Someone without knowledge might think that they are linked but with context you realise that it's Summer and people are hot so they eat Ice cream and go swimming. How would your program deal with the context of the story without jumping to extremely strange conclusions?
What do you expect the player to be using to run the game? As far as i know must methods for interacting with such an AI that you want to develop required quite high end hardware. While most of this will be dependant on you training it (I assume) that there will still be a significant burden on players CPU if they expect to have good response times. You could try offsetting this by using the GPU to do some of the work (see CUDA CUDINN and OpenCL).
What happens when the game is running on a netbook without a GPU? could you get away with adding some story element that would allow for long waiting times between responses? on a different plant to the person that your talking too so you have to wait for the signal to reach them and travel all the way back? (As for as i can remember Earth to Mars is around 12 mins?)
EDIT
I'd also look into old text only games to see how they do it. I think most of they are just multiple choice but some of the lucusArts games had a small box were you could type in a question and based on some keywords it would give you a different response than the standard dialog options. Look into those and think about how an AI would improve those scenarios, Zork, Colossal Cave Adventure, etc. there are lots that have been ported to browser so you can just try them for a bit to get a feel of how they work.
