A senior cabin crewmember here...
The "critical" times for flights is 3 minutes after take-off and 8 minutes before landing. This is the time in which the chance of having an emergency is relatively high, this includes some dangerous maneuvers as a result of rejected take-offs, wind shears, bird strikes, etc.
So, technically speaking if you count 3 minutes after the take-off roll then you are most likely safe enough to recline your seat. However, this is technically speaking and it's not what you should follow.
Legally/policy speaking, you can recline your seat whenever the seat-belt sign is turned off after take off, and placed back upright when the seatbelt sign is turned on for landing, or whenever instructed by the crew. Unlike what others have said, this is the correct indication to follow.
Some airlines allow their cabin crew to move around once the landing-gears are retracted, although moving around the cabin is a bit hard due to the angle of attack, but usually this means the airplane is in a somehow safe situation due to being away from the ground (at least 1,000 feet) and gained some air-speed. Again, this is not for the passengers.
Finally, the pilots have an access to a weather radar and sometimes they see a bad weather ahead so they delay the seatbelt sign because it would make no sense to turn it off for a couple of minutes before turning it again. So none of the "technical guidelines" would do you good, the only thing that will indicate that it is really safe is the seatbelt sign.