I purchased the three way Lutron dimmer switch at a big box store as well (I just read the question about the upside down switch problem); mine dims the light well. IF the other switch to the light is turned on, I can turn the power on/off from the dimmer switch; but if the other switch is not in the ON position, the light does not turn on using the dimmer switch. Please help.
Re-check that the correct wire is connected to the single-side of each switch. For one switch, that's the hot lead from main power. For the other switch, test the voltage levels on all three leads when the switch is removed. Two of the leads will alternate between 120V and nothng when you flip the other switch; the third lead is the output line and that's the one you connect to the single-side of the second switch.
There are lots of diagrams online, and most likely you can get a copy of the one that came with your Lutron switch at their website.