I had the same problem with my Rebel T3i, and through Canon support I found the actual solution.
On the T31, there is a movie mode menu you have to get to. To do so, you have to first put the camera in movie mode, THEN press the menu key. When you do that, a movie menu pops up, and one of the items is "Remote." It will be either enabled or disabled. So you just have to select "enable" and the problem is solved.
So more generally, it appears that the cameras come with the remote disabled by default. You just have to get to the movie menu and re-enable it, and you're good to go.
Not sure what the specifics will be to get there on your camera model, but I think in all likelihood the process will be the same.