OK, following all of these steps worked for me (including Titanium Backup)
How to uninstall avast! Free Mobile Security?
To completely remove avast! Free Mobile Security from your phone, you have to deactivate avast! Anti-Theft at first:
1. Open 'avast! Mobile' from All Apps screen in your Android phone.
2. Select the option 'Anti-Theft', then 'Set up basic settings'.
3. Now ensure that 'Enable Anti-Theft' option is not checked, otherwise clear the checkbox on the right side to deactivate 'avast! Anti-Theft'.
4. Exit the 'avast! Free Mobile Security' user interface.
Once avast! Anti-Theft has been deactivated you can proceed with avast! Anti-Theft and avast! Free Mobile Security uninstallation:
1. Open 'Settings' from All Apps screen in your Android phone.
2. Select the option 'Applications', then 'Manage Applications'.
3. Select the option with disguise-name (custom application name) you chose for avast! Anti-Theft during the installation process.
4. On the next screen 'Uninstall' and then 'OK' to confirm uninstallation of disguised avast! Anti-Theft.
5. Once the uninstallation of avast! Anti-Theft is complete select 'OK' to get back to Manage Applications screen.
6. Select the option 'avast! Mobile Security'.
7. On te next screen 'Uninstall' and then 'OK' to confirm unistallation of disguised avast! Anti-Theft.
8. Once the uninstallation of avast! Free Mobile Security is complete select 'OK' to get back to Manage Applications screen.
Note: These steps can differ slightly depending on your phone type, used operating system version and its vendor customizations.
What can I do if the uninstallation of avast! Anti-Theft doesn't work?
If the uninstallation of avast! Anti-Theft doesn’t work you probably set it as device admin in your phone settings during the configuration. To disable device admin settings for avast! Anti-Theft follow these steps:
1. Open 'avast! Mobile' from All Apps screen in your Android phone.
2. Select the option 'Anti-Theft', then 'Set up advanced settings', then 'Lock text, GPS Wipe' and afterwards 'Device admin' at the bottom of the screen.
3. Now ensure that option with disguise-name (custom application name) you chose for avast! Anti-Theft during the installation is not enabled, otherwise clear the checkbox on the right side to deactivate device admin for 'avast! Anti-Theft'.
4. Exit the 'avast! Free Mobile Security' user interface.
Note: To remove a root installation of avast! Anti-Theft you can use free tool called Titanium Backup which is also alailable on Android Market. You were offered to choose Root installation mode (which requires your phone to be rooted) during the setup process, or continue a normal installation.