This is just a brain dump but feel free to jump in and discuss it or create appropriate wiki pages / sections if you like the ideas presented below.
These suggestions aren't properly thought out so some may be already covered somewhere / do more harm than good / be silly etc. - that's why I'm posting them on my user page and not editing wiki articles just yet ;P
Add to FAQ / General troubleshooting / similar?
Too fresh packages
Solution: the mirrors need to sync up, try again later.
Add info about how to check if a package has just been updated / added to the repos / moved from [testing] - check 'Last Updated' date.
You can download the package directly from the mirror by clicking the 'Download From Mirror' link on the top right e.g.  but remember it doesn't resolve the dependencies, only gets this one package.