Does this script have to run each time the user performs a login or is it a one time deal to get them setup? If it is a one time deal then kees-jan suggestion is the way to correct the current users. Notice that by using the -u option with sudo you execute the script as that user. After that, if you want to do this for each user when they are created then take a look at the /etc/skel directory. It contains the default files that are copied to a users directory when they are created with useradd. This is documented on the useradd man page.
If it needs to happen everytime they login for every user on the system there are several options. You'll want to keep this at the /etc/profile level. You could add the script to /etc/profile, but that will get messy in the long run. A number of distributions have a /etc/profile.d directory where scripts are stored. Inside /etc/profile is a bit of scripting to execute the shell scripts located in that directory.
for i in /etc/profile.d/*.sh ; do
if [ -r "$i" ]; then
You could place your script in that directory and it would be executed for all users whenever they login.
It sounds like this is a global deal and I would stay away from individual user .bash_profile, .bash_login, .profile or whatever shell startup files they have.