Aha!

With the help of my amazing dad, step dad, and brother, I finally found the issue. First of all, scripts cannot utilize setuid in Ubuntu. Thus, when I made a script with setuid to try and bypass using setuid directly with bash, I was doomed to failure. Additionally, when bash detects that it is being run with setuid privileges, it automatically drops its privileges, which explains the different prompt that was displayed with setuid. Finally, to test this, I made a program, not a script, that simply creates a file in the root folder, gave it setuid permissions and made it belong to root. I ran it and it worked, proving that there is no issue with setuid on my computer. I also found a great article at Vidar's Blog that explains more about setuid and how it works with bash and scripts. Now, on to more android related material!