Unfortunately, this isn't a solution, but this information might be of help to you.
I think, your problem is that gnome-terminal and eog are attempting to connect to an at-spi D-bus instance socket, which is mis-configured.
How D-bus works in general:
Start-up
There are 2 instances of casual D-bus, running on your machine, per-system and per-user, and a special accessibility-related one - at-spi, started by at-spi-bus-launcher.
Per-system instance is started by init scripts, e.g. on Mint with /etc/init/dbus.
Per-user instance is run, when Xsession starts /etc/X11/Xsession.d/75dbus_dbus-launch.
at-spi instance seems to be started by gnome-session, which reads .desktop files from the system $xdg directory. At-spi is configured by /etc/xdg/autostart/at-spi-dbus-bus.desktop, which starts at-spi instance.
Functioning and configuration
D-bus works as a message broker for gnome applications. They can send messages to each other by calling functions of dbus-glib binding (glib is the general Gnome C library, which is used by most gnome applications).
Moreover, applications can send messages to other applications, that were not started yet. In that case dbus may first start ("activate") the recipient service and then deliver message to it (which is often abused by gnome guys to start new processes).
What services D-bus can activate is determined by configuration files in /usr/share/dbus-1/ folder. system-services subfolder is for per-system dbus instance, services - for per-user one.
Note also, that those d-bus instances create a UNIX-domain socket and listen for messages from applications. Applications connect to those sockets on start-up and exchange data with each other via D-bus. Sockets may be mapped to file system (as for per-system instance of D-bus, whose socket is mapped to /var/run/dbus/system_bus_socket) or not.
How to solve your problem (I don't know, actually)
I guess that you messed up the configuration of at-pci instance: either its start-up by gnome-session (/etc/xdg/autostart/at-spi-dbus-bus.desktop) or its socket location.
Unfortunately, I don't have any more concrete ideas of what to do. Could you supply your ps or pstree information, regarding at-pci and gnome-terminal?
Update
I tried to find out the source of your error message:
I've tried grepping the source code of gnome-terminal. grep -r "spi" gnome-terminal/ doesn't give any results; grep -r "dbus" gnome-terminal/ gives some, but they seem to be related to the normal dbus, not at-pci one. So, I believe, gnome-terminal doesn't access at-spi2 directly.
Instead, just some gtk widgets are implicitly calling gail or atk functions, which in turn try to interact with at-spi subsystem and fail to do so, cause you've killed it:
So, I think the solution for you is to restore the following files of at-spi2-core package ( based on dpkg -L at-spi2-core) or just to re-install the whole package:
/usr/lib/at-spi2-core/at-spi-bus-launcher
/usr/lib/at-spi2-core/at-spi2-registryd
/usr/share/upstart/xdg/autostart/at-spi-dbus-bus.desktop
/usr/share/upstart/sessions/at-spi2-registryd.conf
/usr/share/doc/at-spi2-core/README
/usr/share/doc/at-spi2-core/copyright
/usr/share/doc/at-spi2-core/NEWS.gz
/usr/share/dbus-1/services/org.a11y.atspi.Registry.service
/usr/share/dbus-1/services/org.a11y.Bus.service
/etc/at-spi2/accessibility.conf
/etc/xdg/autostart/at-spi-dbus-bus.desktop
/etc/X11/Xsession.d/90qt-a11y
/usr/share/doc/at-spi2-core/changelog.Debian.gz
ALTERNATIVELY, you could try to disable the accessibility by inverting the actions, described here to enable it. (Basically, you'll have to tweak some flags in gconftool-2 as described in "Setting up the accessible application development and test environment" section).
Useless, but interesting info
I've done some more digging in source code of at-spi2-core
README at master/bus/at-spi-bus-launcher.c folder tells that at-spi-bus-launcher is started by per-session instance of dbus as expected. Interestingly, there's also an X windows root window property AT_SPI_BUS, you can find its value via xprop --root command and for me it equals
AT_SPI_BUS(STRING) = "unix:abstract=/tmp/dbus-vGwJEbWTQL,guid=76b894a309e380de6265479c53e8b537"
I don't know, what it is, I expected it to be a socket location, but there's no such file in /tmp for me. :(
Update 2
I think the precise reason of your problem might be that the ordinary per-system dbus sees your /usr/share/dbus-1/services/org.a11y.Bus.service file and is trying to activate it in response to atk calls from gnome-terminal (because your gconf or dconf settings have accessibility enabled and this tells gtk widgets to deliver messages to at-spi). This fails, cause you've removed the at-spi-bus-launcher binary.
What makes me think so is my own experience with Caribou Antler. Caribou is a shitty virtual keyboard, installed with Debian. I've got a Debian 7 tablet, where I installed another virtual keyboard from Ubuntu repository - the awesome OnBoard. The thing is that both keyboards are turned on/off by the same accessibility key in dconf. So if the key is on, both are activated by a click on GtkEntry or GtkTextView so that the shitty Caribou doesn't let my OnBoard work properly. And if I disable accessibility in gconf/dconf, OnBoard is disabled, too. :(
So I did a crude hack and just commented out the contents of my /usr/share/dbus-1/services/org.gnome.Caribou.Antler.service file. Now when dbus is trying to activate Caribou, it fails, while OnBoard is activated ok.
But when I start some graphical app from terminal, such as sublime_text, I receive an error message, which is formatted in a very similar way to yours:
(sublime_text:4797): CARIBOU-CRITICAL **: file caribou-gtk-module.c: line1041: unexpected error: GDBus.Error:org.freedesktop.DBus.Error.ServiceUnknown: The name org.gnome.Caribou.Keyboard was not provided by any .service files (g-dbus-error-quark, 2)
Best Answer
This may be because when you run gnome-terminal out of gnome-terminal all the libraries and other code needed to run the program are already in memory. If the terminal program is not already running then libraries will have to be fetched from disk - which can take some time. Does the slow down occur if you launch a new instance of the terminal program from the icon when you have another instance running already?