I did some looking in the code and when the user is in the root folder the PATH variable is blank.  There is then a function in the DNN core library FriendlyUrlProvider.vb.GetFriendlyQueryString()  that converts the blank/space into a +.  It appears that for some reason yours isn't doing that. 

Here are some things that you can try:

1.  Make sure you have the latest version of .Net 2.0, with all of the service packs installed.

2.  Make sure you are running the correct/latest urlrewrite module.  {DNNROOT}\bin\dotnetnuke.httpmodules.urlrewrite.dll     I am running DNN 4.3.5 (currently the latest version) and my file is versioned 3.2.2.27779

3.  In your host configuration settings, under friendly url's, there is a checkbox to turn off friendly urls.  Give that a try.

4.  Manually upload/configure your gallery.  It isn't as nice as using web interface, but you can copy the files up into directories and the gallery module will automatically add them.

Let me know what happens......

I am not sure if you have fixed this already. I have got a similar problem in my DNN 4.3.7 + Gallery 3.01.12 version. I created a test DNN site using the starter kit and came up with the same error when trying to add an album in the gallery.

Then I noticed the url is the following:

http://localhost:3432/DotNetNuke%20Website2/Test/tabid/54/ctl/AlbumEdit/mid/378/path/+/currentstrip/1/action/addfolder/Default.aspx

Then I manually deleted the portion path/+/ and then I am able to create the first album!