I'm assuming you're using RSGallery2 2.2.1 on Joomla 1.5.26. You are using Joomla SEF and in the RSGallery2 Configuration you have set "Advanced SEF" to "Yes (using number and alias, no need for unique aliases)" or "Yes".

The name "Bali Kids : Safari Park Visit" is not a problem, at least it works on my system. The link either gets to be .../photos/20-bali-kids--safari-park-visit or ../photos/gallery/Bali%20Kids%20-%20Safari%20Park%20Visit (where the menu item is called "photos".

The error message originates in the router.php: RSG2 tries to get the gallery id number by using the gallery name, however, it does not find any galleries with that name.

Could you try with a simple gallery name like "test"?
Could you give your system details? See this post: http://www.rsgallery2.nl/rsgallery2_2.x_bugs_problems/posting_rules_16637.msg43162.html

Could you give the rest of the System Details as well (Backend > Help > System Info > System Info)?
Please also upgrade to the latest Joomla version. Although that might not help with this problem, 1.5.26 is a security update.

Are you indeed only using Joomla SEF? Or do you use a third party SEF component?
And what is the SEF setting in the RSGallery2 Configuration?

The name "high_tea_001:1" is not a problem when I use it.

For the "Advanced SEF (all gallery names and item titles must be unique)" there are three options
1. No
2. Yes
3. Yes (using number and alias, no need for unique aliases)

You started with option 2. (Yes) and you had a problem, option 1. (No) doesn't give a problem. Does options 3 give a problem or not?

I double checked the "duplicate item name" since in the code the name given is search in the database. If there is not exactly 1 (no more, no less) entry, RSG2 checks if there are no entries, and it gives the error you got, else there are more than one entries with the same item name. That one, correctly, gives an error message about duplicate names. Something happens with the gallery/item name not being found that I cannot reproduce (yet?).