Can't replace "Proudly powered by WordPress" Text at the bottom of network sites

Hey guys... I'm hoping to get some help for something I'm sure is quite simple. I can't seem to find any answer yet on this forum so if it's been answered already, I'm sorry.

I'm trying to replace the text at the bottom of every multisite sub site. The text I want to replace, is the "Proudly powered by WordPress" text. I understand that this is a link as well, at the bottom of the site. I want this part branded with my own brand instead.

I tried using the Ultimate Branding plugin to do it, because this article says I can (actually says it quite directly).

However, I can't seem to do it at all. If I use the Global footer text add on, it adds it to the very bottom of the pages, and look terrible when displayed. It also adds content to the footer, not replacing the existing one.

Then I thought I'd use that Text Replace add on that's on there, and replace any instance of "Proudly powered by WordPress" - But that doesn't work either. Nothing happens. I then tried to include the anchor tags in the text as well, telling it to replace this text:
<a href="http://wordpress.org">Proudly powered by WordPress</a>
With this text:
Supercharged by <a href="http://pryormedia.net">Pryor Media</a>

Still no luck. In fact this command actually appears to break a lot of things, since half of the text within windows goes missing and regular buttons that are used around the site (like submitting comments) also breaks when I try this.

In between attempts, I'm using several browsers with caching cleared and disabled, I've cleared W3 Total Cache everywhere as well, and have restarted php5-fpm to dump opcache as well as restarted NGinx (although that last step probably doesn't help at all anyways).

Still no luck. How can I rebrand this on every theme network wide always, so that I never see it anywhere?

Thanks for your time folks.

- Charlie