I think that in your case, there is the problem with the specific subfolder /blog and /solutions where it might be mapped or somehow conflicting with existing folders / components / whatever in your site.
Because e.g.
interactiveonline.com/anything/not-here shows the correct URL although also using a sub-folder scheme.
I think that Joomla tries from somereason hand all /blog/* URLs to some component that either does not exists or fails when handling the URL. Maybe you can try changing the value "Parse Joomla SEO links?" in JoomSEF configuration, alternativelly "Redirect nonSEF URLs to SEF?" (but this one should not have effect in your case).
Also make sure there do not exists any special RewriteRules or redirects in your .htaccess or webserver configuration.
