I have a working Mambo 4.5.1 with Gallery 1.4.4 at
http://avinator.com
The component install script included with Gallery 1.4.4 in the /Contrib/Mambo/ folder works GREAT. Additionally, the upload script is fine, and form based uploading works great under Mozilla (problem in Gallery 1.4.3).
Anyways, this is what my settings are like:
/mambo
/mambo/gallery
(*note here: when installing Gallery, select Mambo instead of stand alone)
/mambo/gallery/albums
/mambo/gallery/temporary
I didn't put Gallery into the com_gallery folder. I've installed Gallery on 3 sites, and I always put it in the /mambo/gallery directory.
Install like a normal component, but instead of uploading a zip file, just point the installer to the /mambo/gallery/contrib/mambo/ directory. the install script is there.
gluck.
ps: my favorite galleries are (in order) Gallery 1.4.4, Zoom Media Gallery, Coppermine (never got it working with mambo), AkoGallery, RSgallery (dropped).
EDIT: ps, I forgot, but Gallery's install script creates a mos_ table. so you may want to change that if you changed your db prefix for Mambo.