I encountered this problem once. I had powered down the trackpad in an effort to conserve the batteries, and when I powered it back on (immediately after powering on my Bluetooth keyboard), it wouldn't connect to the computer. I couldn't manually connect it, either.
I tried to delete the trackpad from my Bluetooth devices and then re-pair, but the trackpad refused. It would show up briefly in the Bluetooth devices scan after powering it on, but I would always receive an error that pairing had failed. No amount of powering it on or off (nor waiting between power cycles) changed the behavior.
The solution was to go to the System Preferences, Trackpad, and then select "Set Up Bluetooth Trackpad..." Power on the trackpad, select it when it appears, and that should do it. I don't know why pairing worked when done through the Trackpad preferences and not through Bluetooth settings (which was how I had paired it originally). Either way, it hasn't happened since then.
This was all under OS X 10.8.1 with a late 2011 Macbook Pro.