I've read a few threads about Leopard keeping stale DNS entries (and needing to be manually flushed by some folks periodically to encourage it to do new lookups from their ISP's DNS server, rather than coughing-up potentially out-of-date entries they had looked up earlier and cached). I don't know much specifically about the issue (none of my Macs have made the leap forward to Leopard yet), but maybe do a forum search along those lines and see if it turns up anything helpful.
On another tack, is your Mac using the same DNS server(s) as your other machines on your LAN (ie have you specified a different DNS between the working machines and non-working machines? FWIW, I have had sporadic issues here with my ISP (a very large one in Australia) having their DNS swamped and become intermittently non-responsive, so a month or so ago I moved across to use DNS servers provided by the people at
http://www.opendns.com - I have their DNS server addresses specified in my router, and then all the Macs (and sundry other computers, games consoles, etc) pick these up by default. If the issue turns out to be that your ISP has stale lookup entries for LogMeIn.com (and it seems that
someone does - the question is whether it is a cache on your Mac or at your ISP that is the source of the stale lookup), maybe try changing it, at least temporarily, rather than needing for force your way to LogMeIn.com by the direct IP address.
ted.h.