That's exactly what seems to happen, but the thing is, this account is 
hosted on the same server, on the same domain. So Horde can connect to 
the server and login, but once logged in, it can't connect any more.
I would start with logging.
Which commands are called?
Which error was returned? HTTP? PHP? IMAP?

Everything you've told me so far indicates that the server is not 
reachable from your PHP server.

IMAP debug information should be output to the debug log of the master 
server (i.e. login IMAP server).  If you are not seeing anything in 
there then your configuration is wrong.

Any suggestions on how to make the wording better are welcome, but it 
sounds like an accurate description of your problem.

I get this message:
"Automatic configuration of the account failed. Please check your 
settings or otherwise use the Advanced Setup to manually enter the 
remote server configuration."

And I don't see anything in any of the logs (horde, mail server)

And what happens when you don't use advanced mode and enter your 
password in the config?

I should clarify...
I've used the advanced config form in the prefs to fill in everything. 
I've tried various combinations and the form always accepts my details 
(advanced doesn't ask for a password)

Then I go to IMP and click on the new account. I'm asked for my 
password and then I see the red notification box.

In a red notification, at the bottom right of the screen, right after 
I type in my password.

Where/How do you get that message?

I've tried to get remote accounts to work, but all I get is a notification:
"Could not find remote server configuration"

There is nothing in the Horde or mail server logs, so I have 
absolutely no idea what goes wrong.

Some logging and perhaps more useful error messages could help users 
configure their remote accounts properly