You can get this message if you don't have a data plan or if your carrier doesn't have an agreement with Yahoo. Some carriers don't so you should contact your carrier for resolving this kind of issue.
In case your on AT&T:
AT&T blocks the service books for Yahoo Messenger on BlackBerries.