Whatever "protection" there is may make it hard to access files on the drive now, but shouldn't hinder formatting it. You can use GParted to format the drive in Ubuntu, if Disk Utility doesn't work.
FAT32 is likely fine for your needs. You can only have files under 4 GiB in size on a FAT32 system, though.
NTFS will also work.
There are drivers to access ext2, ext3, and ext4 filesystems on Windows, but if the purpose of this drive is to share data between the systems, you may as well use FAT32 or NTFS. Then you don't have to install any new drivers on any system. Plus, this will let you read and write to the drive on other Windows systems.
In case it's a relevant consideration for you, Mac OS X (without added drivers) will read and write FAT32 and will read but not write NTFS.