The reason you are getting those messages on the transitions is that there is no media left to fill the dissolves. It is, as you say, just putting one clip over the other, but if one or both are using the very first or last frame of the clip then when the app looks for media to fill the dissolve with motion then there isn't any there. Some apps will shorten your media to make it work, some will put in a freeze frame through the dissolve.
The reason it works if you pull one clip back 1:00 and add a 1 second dissolve is that you have essentially shortened the length of that clip by moving it backwards and using the first second for the dissolve. Internally we always choose not to automatically move clips back or trim clips because it does have an impact on the overall length of your timeline and in cases with long audio clips below, it will effect inter-track sync.
So the easy solution is to shoot 1 second longer than you need to, and always pre-trim enough for transitions before adding to the timeline.
Hope this helps make it clearer what's happening, not more muddy