The 3GS must be currently jailbroken at 3.0 or 3.0.1 in order for this to work.
As I read the question, the poster has updated to official 3.1 and is not currently jailbroken.
It is expected that new JB tools for phones already at official 3.1 will be released soon.