Here's some notes and a possible workaround for anyone encountering this.
The problem seems to be related to the individual elements that you allow within your excerpt... I can't really nail down exactly what's causing this, but every time I tried to allow individual elements (b, strong, img, a, etc...), it added the "Read More" link inside the first formatted element that it found...
ie: if I allowed "strong" and I used "strong" text in my excerpt, it added the link inside the "strong" tag. Lame. Same story for links and a handful of other elements that I tried out. EXCEPT for images... if I have an image in my excerpt and I just allow the "img" element, it works just fine... so maybe this is an issue only with formatted text elements that require the HTML markup to both open and close... not self-closing elements like images, HRs, etc... This is frustrating because this is pretty much the main reason most people use this plugin, but hey, I'll take the images.
I worked around this by just stripping the formatted text elements that I wanted to add... which is a step backwards, but still allows me control over how many characters are used and the other features that the plugin still does well.
Hopefully the plugin author will be able to release an update to fix this :) Pretty please? I understand a WP update may have screwed this up, so it's totally understandable if it takes time to get around to fixing this. If you get to this, you rock!
Thanks to this thread for the solution (or at least a workaround): http://wordpress.org/support/topic/plugin-advanced-excerpt-read-the-rest-appears-first-if-graphiclink-if-first-in-document