Have you tried configuring the xdg-open handlers?
Also, have you ensured you have a browser installed on your server? Installing a new browser with apt-get install <browser> should automatically make xdg-open aware of it. However, your setup may not have done this depending on the order that your browser/xdg-utils were installed.
To make things sane again requires running xdg-settings.
To set an http:// handler to your preferred browser (which on a headless server is likely to be w3m, lynx or elinks), do the following:
xdg-settings set default-web-browser w3m.desktop
To verify, you can run xdg-open https://stackoverflow.com/questions/24683221 and you should see your answer in w3m.
If you don't have w3m available, install it with sudo apt-get install w3m
You may wish to see other available handlers by running xdg-settings --list, which on my system, outputs the following:
Known properties:
default-url-scheme-handler Default handler for URL scheme
default-web-browser Default web browser
EDIT:
It turns out that some old systems (ubuntu 10.04) don't have xdg-settings, and that the update-alternatives command should automatically configure xdg-open. Like so:
sudo update-alternatives --config www-browser