For us, this happened with IE7 when it was in "tabbed browsing mode". We went into the browser settings and disabled tabbed browsing and the problem went away.
Never open any browsers before you open QTP - QTP must be opened first.
There should only be one browser open. If there are two, QTP may not be able to tell which one you want, and it will often just say "object not found" when you try to do something on one browser with a 2nd browser open.
Also, if you use dual monitors, make sure the browser is on your primary monitor (usually the same one as your windows task bar). QTP doesn't like interacting with anything running on the secondary monitor (but QTP can be on the secondary monitor just fine - as long as your browser is on the primary monitor).