Remove numbers from filenames

To list all files start with number in a directory,

find . -maxdepth 1 -regextype "posix-egrep" -regex '.*/[0-9]+.*\.mp3' -type f

Problem with your approach is that the find returns a relative path of a file and you are just expecting a filename itself.

Here's something you could do using only bash, with a regex in a conditional:

#! /bin/bash

# get all files that start with a number
for file in [0-9]* ; do
    # only process start start with a number
    # followed by one or more space characters
    if [[ $file =~ ^[0-9]+[[:blank:]]+(.+) ]] ; then
        # display original file name
        echo "< $file"
        # grab the rest of the filename from
        # the regex capture group
        newname="${BASH_REMATCH[1]}"
        echo "> $newname"
        # uncomment to move
        # mv "$file" "$newname"
    fi
done

When run on your sample file names, the output is:

< 01 American Idiot.mp3
> American Idiot.mp3
< 01 Articolo 31 - Domani Smetto.mp3
> Articolo 31 - Domani Smetto.mp3
< 01 Bohemian rapsody.mp3
> Bohemian rapsody.mp3
< 01 Eye of the Tiger.mp3
> Eye of the Tiger.mp3
< 04 Halo.mp3
> Halo.mp3
< 04 Indietro.mp3
> Indietro.mp3
< 04 You Can't Hurry Love.mp3
> You Can't Hurry Love.mp3
< 05 Beautiful girls.mp3
> Beautiful girls.mp3
< 16 Apologize.mp3
> Apologize.mp3
< 16 Christmas Is All Around.mp3
> Christmas Is All Around.mp3

On Debian, Ubuntu and derivatives, use the rename perl script.

To simulate the rename operation:

    rename 's/^\d+ //' * -n

Remove the -n (no act) to perform the operation:

    rename 's/^\d+ //' *

With a little luck perl rename is installed as /usr/bin/rename on your distribution, too (Rumour has it that Fedora also uses perl rename).

See the perl rename man page for more details on other features.