When I remove vim-tiny,
it says ubuntu-minimal will be removed too,
but ubuntu-minimal is important (https://help.ubuntu.com/community/MetaPackages):
ubuntu-minimal: This package depends on all of the packages in the Ubuntu minimal system, that is a functional command-line system with the following capabilities: Boot, Detect hardware, Connect to a network, Install packages, and Perform basic diagnostics. It is also used to help ensure proper upgrades, so it is recommended that it not be removed.
I think this is probably a bug.
ProblemType: Bug
DistroRelease: Ubuntu 12.04
Package: vim-tiny 2:7.3.429-2ubuntu2
ProcVersionSignature: Ubuntu 3.2.0-24.37-generic-pae 3.2.14
Uname: Linux 3.2.0-24-generic-pae i686
ApportVersion: 2.0.1-0ubuntu7
Architecture: i386
Date: Sat May 12 10:44:53 2012
InstallationMedia: Ubuntu 12.04 LTS "Precise Pangolin" - Release i386 (20120423)
ProcEnviron:
TERM=xterm
PATH=(custom, no user)
LANG=en_US.UTF-8
SHELL=/bin/bash
SourcePackage: vim
UpgradeStatus: Upgraded to precise on 2012-05-05 (6 days ago)
(1) This is not a "bug," per sé; vim-tiny is a dependency of ubuntu-minimal, so it makes sense that APT would want to remove ubuntu-minimal if you removed vim-tiny.
(2) Now that we've established that this isn't a bug, in the past, it has been requested, namely in Bug #100029, that vim-tiny be removed from ubuntu-minimal's dependencies, but it was marked as "Won't Fix." Thus, I will mark this as a duplicate of that bug, as this bug seems to imply as well that vim-tiny should not be a dependency of ubuntu-minimal. Please note, however, the related Bug #908132, which recommends that ubuntu-minimal depend on a meta package rather than vim-tiny.
Hope this helps!