Freemium works - and works VERY well.
All you have to do is look at the say AVG, Avira & Teamviewer - they are making hundreds of millions in revenues (and very profitable) .. and I know for a fact as I am in the industry.
AVG & Avira do well in freemium - EVEN considering they have a cost (minute cost) per free user in bandwidth (virus definition updates).
Yes - Freemium can (WILL) cannibalize some of your sales but ALWAYS keep in mind the reason WHY you're going freemium. It's to seed the market and get to people that you're not getting to with your current marketing efforts (or wayyy too expensive to get to them).
If you put out a freemium product and you don't have a really good marketing plan to spread the freemium out really wide then you will end up with cannibalization. You need to get hundreds of thousands of users to install the freemium. What I mean is if with the freemium you are reaching the same exact people you would reach with the paid version than freemium is a useless exercise.
Don't forget - Freemium is a marketing exercise - a way how to get 'cheap' marketing.
Don't forget that freemium is also a great way to get to the SMB drag effect - i.e. home users get it for free and over time the SMBs will be dragged along and buy it.
Ok - now your problem is that you have 30k free users that you would like to convert more of.
Is there at least a way how to tell these users that there is a new version of the free software? If yes - then I would do the following:
Make a new version (minor or major number) that has a way how the product can 'call home' plus also a component that you can send messages to the desktop through your system. I.e. the free version calls home, checks if there are any new messages and if it does display them to the user (look at Avira for an example on how they do it).
I would also make strong statements in the product that the freeware version cannot be used for commercial use. YES - there will be companies that will cheat and use it anyway - but that's ok - frankly - if someone is going to cheat and use software i prefer he uses mine instead of a competitor's. These type of guys are still good to have in your ecosystem, if they like the product they will be part of your 'word-of-mouth' campaigns (especially if it's at no-cost to you).
If there is absolutely no way in getting in touch with those 30,000 users (i.e. not even a new version update) then maybe you should just forget about those and go on with your new plan.
Decide if you still want to go ahead with the freemium model and this time try to get it right - less features (BUT STILL PROVIDES VALUE) with proper messaging (desktop and/or email) and proper nagging (to buy).
As other readers mentioned - without knowing what the product is it's difficult to get into more details - and also it could be that some things i said don't apply. If you want me to check the product out (install the free version that is) just email me.
P.S. Suggested Reading - Free: The Future of a Radical Price by Chris Anderson