Although your original clips are long enough, there is something Premiere uses called Handles which are applied to the head and tail of a clip.
Handles are applied by Premiere when you set In or Out points during editing. There is a small triangle that appears on the clip which indicates whether there are sufficient handles to apply transitions, if not you will get the error that you mention. If your Clip has a tiny triangle at the Head, and/or Tail, that means that it has zero Frames as Handles. Reset the In & Out Points to get the Handles.
Look up Handles in the help documentation and it should help clarify things.
In days of old, in order to place a transition between two clips, the ends of the clips had to overlap one another (V1 and V2, with Transition track sandwiched between the two) . The amount of overlap determined the duration of the transition. As Premiere now uses single-track editing, you still need "overlap", but you can't "see it" like you used to.
To break it down - if you want a 30-frame dissolve between two clips, you can't simply butt them together in their original state, because their is no overlapping material! You need to trim 15 frames from the END of the first clip, and 15 frames from the BEGINNING of the second clip, then butt them together, then you have the required 30 frames of "overlap" needed to complete the transition.
Hope this makes more sense the way I explained it. So when you get that error message, trim some more from the ends of the clips where you want to put the transition.
Safe Harbor Computers
I agree with GraphiteGal, and for more info on Handles, see this Article: http://forums.adobe.com/message/3727485#3727485
Jeff also has a good explanation of days in the A-B Roll editing.