I had the same troubles, though my ISPconfig based Server worked out of th ebox.
I have another ubuntu system running Horde 5 which had the same problem recently.
I had to put the following directives somewhere in my apache conf.
Yours is missing these specific directives:
AllowOverride Options Fileinfo
allow from all
And additionally I have in hordes base conguration Pretty URLs with mod_rewrite enabled.
I hope this points you in the proper direction and you will solve your problem.